{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Pairs of Points With Distance k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计距离为 k 的点对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>二维</strong>&nbsp;整数数组&nbsp;<code>coordinates</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，其中&nbsp;<code>coordinates[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;是第 <code>i</code>&nbsp;个点在二维平面里的坐标。</p>\n",
    "\n",
    "<p>我们定义两个点&nbsp;<code>(x<sub>1</sub>, y<sub>1</sub>)</code>&nbsp;和&nbsp;<code>(x<sub>2</sub>, y<sub>2</sub>)</code>&nbsp;的 <strong>距离</strong>&nbsp;为&nbsp;<code>(x1 XOR x2) + (y1 XOR y2)</code> ，<code>XOR</code>&nbsp;指的是按位异或运算。</p>\n",
    "\n",
    "<p>请你返回满足<em>&nbsp;</em><code>i &lt; j</code><em>&nbsp;</em>且点<em>&nbsp;</em><code>i</code><em> </em>和点<em>&nbsp;</em><code>j</code>之间距离为<em>&nbsp;</em><code>k</code>&nbsp;的点对数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>以下点对距离为 k ：\n",
    "- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。\n",
    "- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>任何两个点之间的距离都为 0 ，所以总共有 10 组点对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= coordinates.length &lt;= 50000</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-pairs-of-points-with-distance-k](https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-pairs-of-points-with-distance-k](https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[4,2],[1,3],[5,2]]\\n5', '[[1,3],[1,3],[1,3],[1,3],[1,3]]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "int n = nums1.size();\n",
    "        for(int i=0;i<nums1.size();i++){\n",
    "            nums1[i]-=nums2[i];\n",
    "        }\n",
    "        sort(nums1.begin(),nums1.end());\n",
    "        int left=0,right = n-1;\n",
    "        long long res = 0;\n",
    "        while(left<right){\n",
    "            long long target = nums1[left]+nums1[right];\n",
    "            if(target>0) {\n",
    "                res+=right-left;\n",
    "                right--;\n",
    "            } else{\n",
    "                left++;\n",
    "            }\n",
    "        }\n",
    "        return  res;\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            nums1[i] = nums1[i] - nums2[i]\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        res = 0\n",
    "        while left<right:\n",
    "            target = nums1[left]+nums1[right]\n",
    "            if target>0:\n",
    "                res = res+right - left\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        res = [nums1[i] - nums2[i] for i in range(n)]\n",
    "        res.sort()\n",
    "        l, r = 0, n - 1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            while r > l and res[l] + res[r] > 0:\n",
    "                r -= 1\n",
    "            ans += n - r - 1\n",
    "            l += 1\n",
    "            if l >= r:\n",
    "                ans += (n - l - 1) * (n - l) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        arr = sorted(x - y for x, y in zip(nums1, nums2))\n",
    "        ans = 0\n",
    "        for x in arr:\n",
    "            ans += n - bisect_right(arr, -x) - (x > 0)\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        sl = SortedList()\n",
    "        for i in range(n):\n",
    "            tmp = nums1[i] - nums2[i]\n",
    "            idx = sl.bisect_left(tmp)\n",
    "            ans += idx \n",
    "            sl.add(-tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        diff = sorted([nums1[i] - nums2[i] for i in range(len(nums1))])\n",
    "        l, r = 0, len(nums1)-1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            if diff[r] + diff[l] > 0:\n",
    "                ans += (r-l)\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # n=len(nums1)\n",
    "        dif = sorted([nums1[j]-nums2[j] for j in range(len(nums1))])\n",
    "        return sum(len(nums1)-max(j+1,bisect_right(dif,-dif[j])) for j in range(len(nums1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = Counter(chain(*edges))\n",
    "        cnt = Counter((min(x, y), max(x, y)) for x, y in edges)\n",
    "        a = sorted(deg[x] + deg[y] for x, y in cnt)\n",
    "        b = sorted(deg[x] + deg[y] - cnt[x, y] for x, y in cnt)\n",
    "        sd = sorted(deg.values())\n",
    "        m = len(sd)\n",
    "        return [(n - m) * (m - bisect_right(sd, q)) + m * m - sum(bisect_right(sd, q - x, i + 1) for i, x in enumerate(sd)) + bisect_right(a, q) - bisect_right(b, q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = Counter(chain(*edges))\n",
    "        cnt = Counter(tuple(sorted(t)) for t in edges)\n",
    "        a = sorted(deg[x] + deg[y] for x, y in cnt)\n",
    "        b = sorted(deg[x] + deg[y] - cnt[x, y] for x, y in cnt)\n",
    "        sd = sorted(deg.values())\n",
    "        m = len(sd)\n",
    "        return [(n - m) * (m - bisect_right(sd, q)) + m * m - sum(bisect_right(sd, q - x, i + 1) for i, x in enumerate(sd)) + bisect_right(a, q) - bisect_right(b, q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        nums=[0 for _ in range(n+1)]\n",
    "        d=Counter(tuple(sorted(e)) for e in edges)\n",
    "        print(le)\n",
    "        for li in edges:\n",
    "            nums[li[0]]+=1\n",
    "            nums[li[1]]+=1\n",
    "            if li[0]>li[1]:\n",
    "                li[0],li[1]=li[1],li[0]\n",
    "                \n",
    "        ans=[0 for _ in queries]\n",
    "        nso=sorted(nums)\n",
    "        for j,q in enumerate(queries):\n",
    "            l,r,a=1,n,0\n",
    "            while l<=r:\n",
    "                if nso[l]+nso[r]<=q:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    a+=r-l\n",
    "                    r-=1\n",
    "            for (x,y),value in d.items():\n",
    "                if q<nums[x]+nums[y]<=q+value:\n",
    "                    a-=1\n",
    "            ans[j]=a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = Counter()\n",
    "        edgesCount = [0 for _ in range(n)]\n",
    "        for (x,y) in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            edgesCount[x]+=1\n",
    "            edgesCount[y]+=1\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            d[x * n + y] += 1\n",
    "        sortedges = sorted(edgesCount)\n",
    "        ans = []\n",
    "        for querie in queries:\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                index = bisect_right(sortedges, querie - sortedges[i], i+1)\n",
    "                total += n - index\n",
    "            for (idx,val) in d.items():\n",
    "                x, y = idx//n, idx%n\n",
    "                if edgesCount[x] + edgesCount[y] > querie and edgesCount[x] + edgesCount[y] - val <= querie:\n",
    "                    total-=1\n",
    "            ans.append(total)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        deg = [0] * (n+1)\n",
    "        for x,y in edges:\n",
    "            deg[x]+=1\n",
    "            deg[y]+=1\n",
    "        \n",
    "        cnt_e = Counter([tuple(sorted(e)) for e in edges])\n",
    "        ans = [0]*len(queries)\n",
    "        sorted_deg = sorted(deg)\n",
    "        for j,q in enumerate(queries):\n",
    "            left,right=1,n\n",
    "            while left<right:\n",
    "                if sorted_deg[left] + sorted_deg[right] <= q:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans[j] += right - left\n",
    "                    right -= 1\n",
    "            for (x,y),c in cnt_e.items():\n",
    "                if q<deg[x]+deg[y]<=q+c:\n",
    "                    ans[j]-=1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degrees = [0] * (n + 1)\n",
    "        edge_cnt = defaultdict(int)\n",
    "        for u, v in edges:\n",
    "            if u > v:\n",
    "                u, v = v, u\n",
    "            degrees[u] += 1\n",
    "            degrees[v] += 1\n",
    "            edge_cnt[u << 16 | v] += 1\n",
    "\n",
    "        sorted_degrees = sorted(degrees)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            l, r = 1, n\n",
    "            while l < r:\n",
    "                if sorted_degrees[l] + sorted_degrees[r] <= q:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    ans[i] += r - l\n",
    "                    r -= 1\n",
    "            for k, c in edge_cnt.items():\n",
    "                u, v = k >> 16, k & 0xffff\n",
    "                if q < degrees[u] + degrees[v] <= q + c:\n",
    "                    ans[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # degree = [0 for _ in range(n)]\n",
    "        # m, cnt = len(edges), {}\n",
    "        # for i in range(m):\n",
    "        #     l, r = edges[i]\n",
    "        #     degree[l - 1] += 1  # 记录每个节点的度\n",
    "        #     degree[r - 1] += 1\n",
    "        #     if l > r:  l, r = r, l\n",
    "        #     if (l, r) not in cnt:   # 记录节点的边数\n",
    "        #         cnt[(l,r)] = 1\n",
    "        #     else:\n",
    "        #         cnt[(l,r)] += 1\n",
    "\n",
    "        # answers = [0 for _ in range(len(queries))]\n",
    "        # numbers = []\n",
    "        # for i in range(n - 1):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if (i + 1, j + 1) in cnt:\n",
    "        #             numbers.append(degree[i] + degree[j] - cnt[(i + 1,j + 1)])\n",
    "        #         else:\n",
    "        #             numbers.append(degree[i] + degree[j])\n",
    "\n",
    "        # for q in range(len(queries)):\n",
    "        #     for i in range(len(numbers)):\n",
    "        #         if numbers[i] > queries[q]:\n",
    "        #             answers[q] += 1\n",
    "        # return answers\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degree = [0 for _ in range(n)]\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for edge in edges:\n",
    "            x, y = edge[0] - 1, edge[1] - 1\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "            cnt[x * n + y] += 1\n",
    "\n",
    "        arr = sorted(degree)\n",
    "        ans = []\n",
    "        for bound in queries:\n",
    "            total = 0\n",
    "            j = n - 1\n",
    "            for i in range(n):\n",
    "                while j > i and arr[i] + arr[j] > bound:\n",
    "                    j -= 1\n",
    "                total += n - 1 - max(i, j)\n",
    "            for val, freq in cnt.items():\n",
    "                x, y = val // n, val % n\n",
    "                if degree[x] + degree[y] > bound and degree[x] + degree[y] - freq <= bound:\n",
    "                    total -= 1\n",
    "            ans.append(total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degree = [0 for _ in range(n)]\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for edge in edges:\n",
    "            x, y = edge[0] - 1, edge[1] - 1\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "            cnt[x * n + y] += 1\n",
    "\n",
    "        arr = sorted(degree)\n",
    "        ans = []\n",
    "        for bound in queries:\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                j = bisect_right(arr, bound - arr[i], i + 1)\n",
    "                total += n - j\n",
    "            for val, freq in cnt.items():\n",
    "                x, y = val // n, val % n\n",
    "                if degree[x] + degree[y] > bound and degree[x] + degree[y] - freq <= bound:\n",
    "                    total -= 1\n",
    "            ans.append(total)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] *(n+1)\n",
    "        for x,y in edges:\n",
    "            deg[x] +=1\n",
    "            deg[y] +=1\n",
    "        # 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边\n",
    "        cnt_e = Counter(tuple(sorted(e)) for e in edges)#类比哈希表\n",
    "\n",
    "        ans = [0]*len(queries)\n",
    "        sorted_deg = sorted(deg)\n",
    "        for j,q in enumerate(queries):\n",
    "            left,right =1,n\n",
    "            while left<right:\n",
    "                if sorted_deg[left] +sorted_deg[right] <=q:\n",
    "                    left +=1\n",
    "                else:\n",
    "                    ans[j]+=right-left\n",
    "                    right -=1\n",
    "            for (x,y) ,c in cnt_e.items():\n",
    "                if q<deg[x]+deg[y] <=q+c:\n",
    "                    ans[j] -=1\n",
    "        return ans \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg=[0]*(n+1)\n",
    "        for x,y in edges:\n",
    "            deg[x]+=1\n",
    "            deg[y]+=1\n",
    "        cnt_e=Counter(tuple(sorted(e)) for e in edges)\n",
    "\n",
    "        ans=[0]*len(queries)\n",
    "        sorted_deg=sorted(deg)\n",
    "        for j,q in enumerate(queries):\n",
    "            left,right=1,n\n",
    "            while left<right:\n",
    "                if sorted_deg[left]+sorted_deg[right]<=q:\n",
    "                    left+=1\n",
    "                else:\n",
    "                    ans[j]+=right-left\n",
    "                    right-=1\n",
    "            for (x,y),c in cnt_e.items():\n",
    "                if q<deg[x]+deg[y]<=q+c:\n",
    "                    ans[j]-=1\n",
    "        return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * (n + 1)\n",
    "        cnt_e = dict()  # 比 Counter 快一点\n",
    "        for x, y in edges:\n",
    "            if x > y: x, y = y, x\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            cnt_e[(x, y)] = cnt_e.get((x, y), 0) + 1\n",
    "        cnt_deg = Counter(deg[1:])\n",
    "\n",
    "        # 2)\n",
    "        cnts = [0] * (max(deg) * 2 + 2)\n",
    "        for deg1, c1 in cnt_deg.items():\n",
    "            for deg2, c2 in cnt_deg.items():\n",
    "                if deg1 < deg2:\n",
    "                    cnts[deg1 + deg2] += c1 * c2\n",
    "                elif deg1 == deg2:\n",
    "                    cnts[deg1 + deg2] += c1 * (c1 - 1) // 2\n",
    "\n",
    "        # 3)\n",
    "        for (x, y), c in cnt_e.items():\n",
    "            s = deg[x] + deg[y]\n",
    "            cnts[s] -= 1\n",
    "            cnts[s - c] += 1\n",
    "\n",
    "        # 4) 计算 cnts 的后缀和\n",
    "        for i in range(len(cnts) - 1, 0, -1):\n",
    "            cnts[i - 1] += cnts[i]\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = cnts[min(q + 1, len(cnts) - 1)]\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        indegree = [0]*(n+1) \n",
    "        for x,y in edges:\n",
    "            indegree[x] += 1\n",
    "            indegree[y] += 1\n",
    "        \n",
    "        g = collections.Counter(tuple(sorted(e)) for e in edges)\n",
    "        ans = [0] * len(queries)\n",
    "        sorted_deg = sorted(indegree)  # 排序，为了双指针\n",
    "        # print(indegree,sorted_deg)\n",
    "        # print(g)\n",
    "        for i,limit in enumerate(queries):\n",
    "            left = 1 \n",
    "            right = n\n",
    "            while left<right:\n",
    "                if sorted_deg[left] + sorted_deg[right] <= limit:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans[i] += right -left\n",
    "                    right -= 1\n",
    "            for (x,y),cnt in g.items():\n",
    "                if limit<indegree[x]+indegree[y]<=limit+cnt:#必需严格大于limit,因为上面筛选的时候就是这样的\n",
    "                    ans[i] -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # deg[i] 表示与点 i 相连的边的数目\n",
    "        # deg = [0] * (n + 1)  # 节点编号从 1 到 n\n",
    "        # for x, y in edges:\n",
    "        #     deg[x] += 1\n",
    "        #     deg[y] += 1\n",
    "        # # 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边\n",
    "        # cnt_e = Counter(tuple(sorted(e)) for e in edges)\n",
    "\n",
    "        # ans = [0] * len(queries)\n",
    "        # sorted_deg = sorted(deg)  # 排序，为了双指针\n",
    "        # print(deg,sorted_deg)\n",
    "        # for j, q in enumerate(queries):\n",
    "        #     left, right = 1, n  # 相向双指针\n",
    "        #     while left < right:\n",
    "        #         if sorted_deg[left] + sorted_deg[right] <= q:\n",
    "        #             left += 1\n",
    "        #         else:\n",
    "        #             ans[j] += right - left\n",
    "        #             right -= 1\n",
    "                    \n",
    "        #     for (x, y), c in cnt_e.items():\n",
    "        #         if q < deg[x] + deg[y] <= q + c:\n",
    "        #             ans[j] -= 1\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # deg[i] 表示与点 i 相连的边的数目\n",
    "        deg = [0] * (n + 1)  # 节点编号从 1 到 n\n",
    "        for x, y in edges:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        # 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边\n",
    "        cnt_e = Counter(tuple(sorted(e)) for e in edges)\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        sorted_deg = sorted(deg)  # 排序，为了双指针\n",
    "        for j, q in enumerate(queries):\n",
    "            left, right = 1, n  # 相向双指针\n",
    "            while left < right:\n",
    "                if sorted_deg[left] + sorted_deg[right] <= q:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans[j] += right - left\n",
    "                    right -= 1\n",
    "            for (x, y), c in cnt_e.items():\n",
    "                if q < deg[x] + deg[y] <= q + c:\n",
    "                    ans[j] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # deg[i] 表示与点 i 相连的边的数目\n",
    "        deg = [0] * (n + 1)  # 节点编号从 1 到 n\n",
    "        for x, y in edges:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        # 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边\n",
    "        cnt_e = Counter(tuple(sorted(e)) for e in edges)\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        sorted_deg = sorted(deg)  # 排序，为了双指针\n",
    "        for j, q in enumerate(queries):\n",
    "            left, right = 1, n  # 相向双指针\n",
    "            while left < right:\n",
    "                if sorted_deg[left] + sorted_deg[right] <= q:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans[j] += right - left\n",
    "                    right -= 1\n",
    "            for (x, y), c in cnt_e.items():\n",
    "                if q < deg[x] + deg[y] <= q + c:\n",
    "                    ans[j] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degree = [0 for _ in range(n+1)]\n",
    "        cnt = Counter(tuple(sorted(e)) for e in edges)\n",
    "        for e in edges:\n",
    "            degree[e[0]] += 1\n",
    "            degree[e[1]] += 1\n",
    "\n",
    "        sorted_degree = sorted(degree)\n",
    "        \n",
    "        ans = []\n",
    "        for i,d in enumerate(queries):\n",
    "            total = 0\n",
    "            left = 1\n",
    "            right = n\n",
    "            while left<right:\n",
    "                if sorted_degree[left] + sorted_degree[right] <= d:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    total += right - left\n",
    "                    right -= 1\n",
    "            \n",
    "            for (x,y),c in cnt.items():\n",
    "                if degree[x] + degree[y] > d and degree[x] + degree[y] - c <= d:\n",
    "                    total -= 1\n",
    "\n",
    "            ans.append(total)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        nn = 0\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault(mi, dict())\n",
    "            e[mi].setdefault(ma, 0)\n",
    "            e[mi][ma] += 1\n",
    "        z = sorted(cnt)\n",
    "        nn = len(z)\n",
    "        dd = dict()\n",
    "        cc = Counter(cnt)\n",
    "        @lru_cache(n)\n",
    "        def findy(jj, i):\n",
    "            if jj > queries[i]:\n",
    "                return n - 1\n",
    "            yy = bisect_right(z, queries[i] - jj)\n",
    "            return nn - yy - (2 * jj > queries[i])\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for j, ccc in cc.items():\n",
    "                res[i] += findy(j, i) * ccc\n",
    "            for u, vv in e.items():\n",
    "                for edg, v in vv.items():\n",
    "                    if queries[i] < cnt[edg] + cnt[u] <= v + queries[i]:\n",
    "                        res[i] -= 2\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        nn = 0\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault(mi, dict())\n",
    "            e[mi].setdefault(ma, 0)\n",
    "            e[mi][ma] += 1\n",
    "        z = sorted(cnt)\n",
    "        nn = len(z)\n",
    "        dd = dict()\n",
    "        @lru_cache(n)\n",
    "        def findy(jj, i):\n",
    "            if jj > queries[i]:\n",
    "                return n - 1\n",
    "            yy = bisect_right(z, queries[i] - jj)\n",
    "            return nn - yy - (2 * jj > queries[i])\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for j in cnt:\n",
    "                res[i] += findy(j, i)\n",
    "            for u, vv in e.items():\n",
    "                for edg, v in vv.items():\n",
    "                    if queries[i] < cnt[edg] + cnt[u] <= v + queries[i]:\n",
    "                        res[i] -= 2\n",
    "            y = findy(0, i)\n",
    "            res[i] += y * (n - nn)\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        # 枚举O(n log(n) + len(queries)(n+len(edges)))\n",
    "        deg = [0] * (n+1)  # 记录点的邻边数\n",
    "        for x, y in edges:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        sorted_deg = sorted(deg)  # 排序后的点邻边数，有一个点0实际不存在需跳过\n",
    "        count_edge = Counter(tuple(sorted(e)) for e in edges)  # 记录各边数\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            left, right = 1, n\n",
    "            while left < right:\n",
    "                if sorted_deg[left] + sorted_deg[right] <= q:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    ans[i] += right - left\n",
    "                    right -= 1\n",
    "            \n",
    "            for (x, y), c in count_edge.items():\n",
    "                if deg[x] + deg[y] > q and deg[x] + deg[y] - c <= q:\n",
    "                    ans[i] -= 1\n",
    "        return ans\n",
    "        \"\"\"\n",
    "        # 终极优化O(n+len(queries)+len(edges))\n",
    "        # 2m个积木只能搭建约(4m)^(0.5)个不同高度的塔\n",
    "        # 重复计算很多，q里面的值可能一样，可以计算cnt=1, 2, ...的数量，最后后缀和\n",
    "        deg = [0] * (n+1)  # 记录点的邻边数\n",
    "        count_edge = {}  # 记录各边数,{(x, y)出现在edges中的边，x<y: c边数}\n",
    "        for x, y in edges:\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            count_edge[(x, y)] = count_edge.get((x, y), 0) + 1  # 统计edges中各边数量\n",
    "\n",
    "        count_deg = Counter(deg[1:])  # 各邻边数量的点数{邻边数: 对应的点数}\n",
    "        cnt = [0] * (2*max(count_deg) + 2)  # 邻边数为索引的点对数量\n",
    "        for deg1, c_p1 in count_deg.items():\n",
    "            for deg2, c_p2 in count_deg.items():\n",
    "                if deg1 < deg2:  # 避免重复计算\n",
    "                    cnt[deg1+deg2] += c_p1 * c_p2\n",
    "                elif deg1 == deg2:\n",
    "                    cnt[deg1+deg2] += c_p1 * (c_p1-1) // 2  # 点对的两点有重复未去除情况\n",
    "        \n",
    "        for (x, y), c in count_edge.items():  # 点对去重\n",
    "            tmp = deg[x] + deg[y]\n",
    "            cnt[tmp] -= 1\n",
    "            cnt[tmp-c] += 1\n",
    "\n",
    "        for i in range(len(cnt)-2, -1, -1):\n",
    "            cnt[i] += cnt[i+1]\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = cnt[min(q+1, len(cnt)-1)]\n",
    "            print(queries)\n",
    "        return queries\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def encode(self, a: int, b: int, n: int):\n",
    "        return max(a, b) * (n + 1) + min(a, b)\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "\n",
    "        deg = [0] * (n + 1)\n",
    "        overlap = {}\n",
    "        distinctEdges = []\n",
    "        for i in range(edges.__len__()):\n",
    "            x = edges[i][0]\n",
    "            y = edges[i][1]\n",
    "            \n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            idx = self.encode(x, y, n)\n",
    "            if idx not in overlap.keys():\n",
    "                distinctEdges.append((x, y))\n",
    "                overlap[idx] = 0\n",
    "            overlap[idx] += 1\n",
    "        \n",
    "        sortDeg = deg.copy()\n",
    "        sortDeg = sortDeg[1:sortDeg.__len__()]\n",
    "        sortDeg.sort()\n",
    "        \n",
    "        res = []\n",
    "        for i in range(queries.__len__()):\n",
    "            l = 0\n",
    "            r = n - 1\n",
    "            cnt = 0\n",
    "            while l < n:\n",
    "                while r > l and sortDeg[l] + sortDeg[r] > queries[i]:\n",
    "                    r -= 1\n",
    "                cnt += (n - max(l, r) - 1)\n",
    "                l += 1          \n",
    "            for j in range(distinctEdges.__len__()):\n",
    "                x = distinctEdges[j][0]\n",
    "                y = distinctEdges[j][1]\n",
    "                idx = self.encode(x, y, n)\n",
    "                if deg[x] + deg[y] > queries[i] and deg[x] + deg[y] - overlap[idx] <= queries[i]:\n",
    "                    cnt -= 1\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = dict()\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt.setdefault(y[0]-1, 0)\n",
    "            cnt.setdefault(y[1]-1, 0)\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault(mi, dict())\n",
    "            e[mi].setdefault(ma, 0)\n",
    "            e[mi][ma] += 1\n",
    "        z = sorted(cnt.values())\n",
    "        dd = dict()\n",
    "        @lru_cache(n)\n",
    "        def findy(yyy):\n",
    "            return bisect_right(z, yyy)\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for x, j in cnt.items():\n",
    "                if j > queries[i]:\n",
    "                    res[i] += n - 1\n",
    "                    continue\n",
    "                y = findy(queries[i] - j)\n",
    "                res[i] += len(z) - y - (2 * j > queries[i])\n",
    "                for edg in e.get(x, dict()):\n",
    "                    if cnt[edg] + j - e[x][edg] <= queries[i] and cnt[edg] + j > queries[i]:\n",
    "                        res[i] -= 2\n",
    "            y = len(z) - findy(queries[i])\n",
    "            res[i] += y * (n - len(z))\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = Counter()\n",
    "        e = {i:defaultdict(int) for i in range(1,n+1)}\n",
    "        for u,v in edges:\n",
    "            d[u]+=1\n",
    "            d[v]+=1\n",
    "            e[min(u,v)][max(u,v)]+=1\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            cnt = 0\n",
    "            blist = [d[n]]\n",
    "            for i in range(n-1,0,-1):\n",
    "                if q+1-d[i]<=0:\n",
    "                    cnt += len(blist)\n",
    "                else:\n",
    "                    j = bisect_left(blist,q+1-d[i])\n",
    "                    cnt += (len(blist) - j)\n",
    "                    for b in e[i]:\n",
    "                        if d[i]+d[b]>=q+1 and d[i]+d[b]-e[i][b]<q+1:\n",
    "                            cnt-=1\n",
    "                insort(blist,d[i])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = dict()\n",
    "        e = dict()\n",
    "        nn = 0\n",
    "        for y in edges:\n",
    "            cnt.setdefault(y[0]-1, 0)\n",
    "            cnt.setdefault(y[1]-1, 0)\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault(mi, dict())\n",
    "            e[mi].setdefault(ma, 0)\n",
    "            e[mi][ma] += 1\n",
    "        z = sorted(cnt.values())\n",
    "        nn = len(z)\n",
    "        dd = dict()\n",
    "        @lru_cache(n)\n",
    "        def findy(jj, i):\n",
    "            if jj > queries[i]:\n",
    "                return n - 1\n",
    "            yy = bisect_right(z, queries[i] - jj)\n",
    "            return nn - yy - (2 * jj > queries[i])\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for j in cnt.values():\n",
    "                res[i] += findy(j, i)\n",
    "            for u, vv in e.items():\n",
    "                for edg, v in vv.items():\n",
    "                    if queries[i] < cnt[edg] + cnt[u] <= v + queries[i]:\n",
    "                        res[i] -= 2\n",
    "            y = findy(0, i)\n",
    "            res[i] += y * (n - nn)\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        dic=defaultdict(int)\n",
    "        degree={i:0 for i in range(1,n+1)}\n",
    "        for i in edges:\n",
    "            \n",
    "            a,b=i[0],i[1]\n",
    "            degree[a]+=1\n",
    "            degree[b]+=1\n",
    "            a,b=min(a,b),max(a,b)\n",
    "            dic[(a,b)]+=1\n",
    "        items=sorted(degree.items(),key=lambda x:(x[1],x[0]))\n",
    "        keys=[i[0] for i in items]\n",
    "        values=[i[1] for i in items]\n",
    "        res=[]\n",
    "        for i in queries:\n",
    "            total=0\n",
    "            for j in range(len(values)):\n",
    "                cur=values[j]\n",
    "                b=max(j+1,bisect_right(values,i-cur))\n",
    "                total+=n-b\n",
    "            for j in dic:\n",
    "                if degree[j[0]]+degree[j[1]]>i and degree[j[0]]+degree[j[1]]-dic[j]<=i:\n",
    "                    total-=1\n",
    "            res.append(total)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        edgeCnt = collections.Counter()\n",
    "        for a, b in edges:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            deg[a - 1] += 1\n",
    "            deg[b - 1] += 1\n",
    "            edgeCnt[a - 1, b - 1] += 1\n",
    "        degSort = sorted(deg)\n",
    "        m = len(queries)\n",
    "        res = [0] * m\n",
    "        for i, q in enumerate(queries):\n",
    "            cnt = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                if degSort[left] + degSort[right] <= q:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    cnt += right - left\n",
    "                    right -= 1\n",
    "            for a, b in edgeCnt:\n",
    "                if deg[a] + deg[b] > q and deg[a] + deg[b] - edgeCnt[a, b] <= q:\n",
    "                    cnt -= 1\n",
    "            res[i] = cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = dict()\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt.setdefault(y[0]-1, 0)\n",
    "            cnt.setdefault(y[1]-1, 0)\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault(mi, dict())\n",
    "            e[mi].setdefault(ma, 0)\n",
    "            e[mi][ma] += 1\n",
    "        z = sorted(cnt.values())\n",
    "        dd = dict()\n",
    "        @lru_cache(n)\n",
    "        def findy(yyy):\n",
    "            return bisect_right(z, yyy)\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for x, j in cnt.items():\n",
    "                if j > queries[i]:\n",
    "                    res[i] += n - 1\n",
    "                    continue\n",
    "                y = findy(queries[i] - j)\n",
    "                res[i] += len(z) - y - (2 * j > queries[i])\n",
    "            for u, vv in e.items():\n",
    "                for edg, v in vv.items():\n",
    "                    if queries[i] < cnt[edg] + cnt[u] <= v + queries[i]:\n",
    "                        res[i] -= 2\n",
    "            y = len(z) - findy(queries[i])\n",
    "            res[i] += y * (n - len(z))\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(set)\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            e.setdefault(y[0]-1, dict())\n",
    "            e.setdefault(y[1]-1, dict())\n",
    "            e[y[0]-1].setdefault(y[1]-1, 0)\n",
    "            e[y[1]-1].setdefault(y[0]-1, 0)\n",
    "            e[y[0]-1][y[1]-1] += 1\n",
    "            e[y[1]-1][y[0]-1] += 1\n",
    "        z = sorted(cnt)\n",
    "        for i in range(len(queries)):\n",
    "            for x, j in enumerate(cnt):\n",
    "                if j > queries[i]:\n",
    "                    res[i] += n - 1\n",
    "                    continue\n",
    "                y = bisect_right(z, queries[i] - j)\n",
    "                res[i] += len(z) - y - (2 * j > queries[i])\n",
    "                if x in e:\n",
    "                    for edg in e[x]:\n",
    "                        if cnt[edg] + j - e[x][edg] <= queries[i] and cnt[edg] + j > queries[i]:\n",
    "                            res[i] -= 1\n",
    "            res[i] = res[i]// 2\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(set)\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            e.setdefault(y[0]-1, dict())\n",
    "            e.setdefault(y[1]-1, dict())\n",
    "            e[y[0]-1].setdefault(y[1]-1, 0)\n",
    "            e[y[1]-1].setdefault(y[0]-1, 0)\n",
    "            e[y[0]-1][y[1]-1] += 1\n",
    "            e[y[1]-1][y[0]-1] += 1\n",
    "        z = sorted(cnt)\n",
    "        for i in range(len(queries)):\n",
    "            for x, j in enumerate(cnt):\n",
    "                if j > queries[i]:\n",
    "                    res[i] += n - 1\n",
    "                    continue\n",
    "                y = bisect_right(z, queries[i] - j)\n",
    "                res[i] += len(z) - y - (2 * j > queries[i])\n",
    "                for edg in e.get(x, dict()):\n",
    "                    if cnt[edg] + j - e[x][edg] <= queries[i] and cnt[edg] + j > queries[i]:\n",
    "                        res[i] -= 1\n",
    "            res[i] = res[i]// 2\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "\n",
    "        # 统计每个点的连接数量&相互连接数量：O(E)\n",
    "        count_num = [0] * n\n",
    "        count_cross = collections.defaultdict(collections.Counter)\n",
    "        for u, v in edges:\n",
    "            count_num[u - 1] += 1\n",
    "            count_num[v - 1] += 1\n",
    "            count_cross[u - 1][v - 1] += 1\n",
    "            count_cross[v - 1][u - 1] += 1\n",
    "\n",
    "        # 排序连接数量：O(NlogN)\n",
    "        sorted_num = sorted(count_num)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for query in queries:\n",
    "            res = 0\n",
    "\n",
    "            # 统计每个结点可以选择的结点数量\n",
    "            # 每个结点都考虑除自己以外所有的边，最终得出结果的2倍\n",
    "            for i in range(n):\n",
    "                # 如果当前结点的连接的边数已经达到查询要求，则当前结点所有连接的边均符合要求\n",
    "                if count_num[i] > query:\n",
    "                    res += (n - 1)\n",
    "\n",
    "                # 如果当前结点的连接的边数未达到查询要求，则二分查找相邻的符号的点对\n",
    "                else:\n",
    "                    # 计算还需要的边数量\n",
    "                    need = query - count_num[i]\n",
    "\n",
    "                    # 二分查找符合条件的边（暂不考虑点对本身就是一条/多条边；暂不考虑将自身算在内的情况）\n",
    "                    # 单次：O(logN)；累计：O(QNlogN)\n",
    "                    idx = bisect.bisect_right(sorted_num, need)\n",
    "                    res += (n - idx)\n",
    "\n",
    "                    # 将自身剔除（如果被算进去的话）\n",
    "                    if count_num[i] > need:\n",
    "                        res -= 1\n",
    "\n",
    "                    # 处理点对本身就是一条/多条边的情况，如果不足要求则剔除\n",
    "                    # 单次：O(E/N)；累计：O(QE)\n",
    "                    for j in count_cross[i]:\n",
    "                        # 按此前方法计算被计入，但实际上不符合查询要求的情况\n",
    "                        if count_num[i] + count_num[j] > query >= count_num[i] + count_num[j] - count_cross[i][j]:\n",
    "                            res -= 1\n",
    "\n",
    "            ans.append(res // 2)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(set)\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            e.setdefault(y[0]-1, dict())\n",
    "            e.setdefault(y[1]-1, dict())\n",
    "            e[y[0]-1].setdefault(y[1]-1, 0)\n",
    "            e[y[1]-1].setdefault(y[0]-1, 0)\n",
    "            e[y[0]-1][y[1]-1] += 1\n",
    "            e[y[1]-1][y[0]-1] += 1\n",
    "        z = sorted(cnt)\n",
    "        for i in range(len(queries)):\n",
    "            for x, j in enumerate(cnt):\n",
    "                \n",
    "                y = bisect_right(z, queries[i] - j)\n",
    "                res[i] += len(z) - y - (2 * j > queries[i])\n",
    "                for edg in e.get(x, dict()):\n",
    "                    if cnt[edg] + j - e[x][edg] <= queries[i] and cnt[edg] + j > queries[i]:\n",
    "                        res[i] -= 1\n",
    "            res[i] = res[i]// 2\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        lines = [0] * (n + 1)\n",
    "        connect = defaultdict(dict)\n",
    "        for u, v in edges:\n",
    "            lines[u] += 1\n",
    "            lines[v] += 1\n",
    "            if v not in connect[u]:\n",
    "                connect[u][v] = 0\n",
    "            connect[u][v] += 1\n",
    "            if u not in connect[v]:\n",
    "                connect[v][u] = 0\n",
    "            connect[v][u] += 1\n",
    "        # print(lines)\n",
    "        # print(connect)\n",
    "        # freq[i, j] j个点所连接边数量为i\n",
    "        freqs = defaultdict(int)\n",
    "        for i in range(1, n + 1):\n",
    "            freqs[lines[i]] += 1\n",
    "        freqs = [[k, v] for k, v in freqs.items()]\n",
    "        freqs.sort(key=lambda x: x[0])\n",
    "        # print(freqs)\n",
    "        l = len(edges)\n",
    "        # counts[i] 两个点边数之和为i\n",
    "        counts = [0] * (l + 1)\n",
    "        for i in range(len(freqs)):\n",
    "            iline, ipoints = freqs[i]\n",
    "            counts[min(iline * 2, l)] += ipoints * (ipoints - 1) // 2\n",
    "            for j in range(i + 1, len(freqs)):\n",
    "                jline, jpoints = freqs[j]\n",
    "                counts[min(iline + jline, l)] += ipoints * jpoints\n",
    "        # print(counts)\n",
    "        # 根据uv之间的边修正\n",
    "        for u, f in connect.items():\n",
    "            for v, c in f.items():\n",
    "                if u < v:\n",
    "                    counts[min(lines[u] + lines[v], l)] -= 1\n",
    "                    counts[min(lines[u] + lines[v] - c, l)] += 1\n",
    "        # print(counts)\n",
    "        for i in range(l - 1, -1, -1):\n",
    "            counts[i] += counts[i + 1]\n",
    "        # print(counts)\n",
    "        \n",
    "        return [counts[q + 1] for q in queries]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = {}\n",
    "        E = set()\n",
    "        for i in range(n+1):\n",
    "            deg[i] = 0\n",
    "        overlap = {}\n",
    "        ans = []\n",
    "\n",
    "        for e in edges:\n",
    "            sortede = tuple(sorted(e))\n",
    "            deg[sortede[0]] += 1\n",
    "            deg[sortede[1]] += 1\n",
    "            overlap[sortede] = overlap.get(sortede, 0) + 1\n",
    "            E.add(sortede)\n",
    "        \n",
    "        tmpdeg = deepcopy(deg)\n",
    "        deg = deg.items()\n",
    "        deg = sorted(deg, key = lambda x: x[1])\n",
    "        #print(deg)\n",
    "        #Double Pointer\n",
    "\n",
    "        for q in queries:\n",
    "            count = 0\n",
    "            l, r = 1, n\n",
    "\n",
    "            while l < r:\n",
    "                degsum = deg[l][1] + deg[r][1]\n",
    "                #print(l, r, degsum)\n",
    "                if degsum > q:\n",
    "                    count += (r - l)\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "            #print(count)\n",
    "\n",
    "            for edge in E:\n",
    "                sumdeg = tmpdeg[edge[0]] + tmpdeg[edge[1]]\n",
    "                #print(sumdeg, \"sumdeg\", edge)\n",
    "                if sumdeg > q and sumdeg - overlap[edge] <= q:\n",
    "                    #print(edge, overlap[edge], sumdeg)\n",
    "                    count -= 1\n",
    "                    \n",
    "            ans.append(count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]]\n",
    "        # n = 5\n",
    "        # queries = [5]\n",
    "        from sortedcontainers import SortedList\n",
    "        aEdge = defaultdict(list)\n",
    "        adj = Counter()\n",
    "        edgeCounter = Counter()\n",
    "        for u, v in edges:\n",
    "            if u > v:\n",
    "                u, v = v, u\n",
    "            adj[u] += 1\n",
    "            adj[v] += 1\n",
    "            if (u, v) not in edgeCounter:\n",
    "                aEdge[v].append(u)\n",
    "            edgeCounter[(u, v)] += 1\n",
    "        # print(aEdge, adj, edgeCounter)\n",
    "        ret = []\n",
    "        for query in queries:\n",
    "            ans = 0\n",
    "            prev = SortedList()\n",
    "            for u in range(1, n + 1):\n",
    "                ans += prev.bisect_right(adj[u]) - len([v for v in aEdge[u] if query < adj[v] + adj[u] <= query + edgeCounter[(v, u)]])\n",
    "                prev.add(query - adj[u] + 1)\n",
    "                # print(ans, prev, u)\n",
    "            ret.append(ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degrees = [0] * (n + 1)\n",
    "        d = {}\n",
    "        for u, v in edges:\n",
    "            degrees[u] += 1\n",
    "            degrees[v] += 1\n",
    "            if u not in d:\n",
    "                d[u] = {}\n",
    "            d[u][v] = d[u].get(v, 0) + 1\n",
    "            if v not in d:\n",
    "                d[v] = {}\n",
    "            d[v][u] = d[v].get(u, 0) + 1\n",
    "        sorted_degrees = sorted(degrees[1:])\n",
    "        import bisect\n",
    "        res = []\n",
    "        for limit in queries:\n",
    "            cnt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                cnt += n - bisect.bisect_left(sorted_degrees, limit - degrees[i] + 1)\n",
    "                if degrees[i] * 2 > limit:\n",
    "                    cnt -= 1\n",
    "            cnt = cnt // 2\n",
    "            for i in d:\n",
    "                for j in d[i]:\n",
    "                    if i < j and degrees[i] + degrees[j] > limit and degrees[i] + degrees[j] - d[i][j] <= limit:\n",
    "                        cnt -= 1\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        adj = defaultdict(partial(defaultdict, int))\n",
    "        for u, v in edges :\n",
    "            adj[u][v] += 1\n",
    "            adj[v][u] += 1\n",
    "        Vcnt = [0 for i in range(n + 1)]\n",
    "        for k, v in adj.items() :\n",
    "            Vcnt[k] = sum(v.values())\n",
    "\n",
    "        degree = sorted(Vcnt)\n",
    "        res = []\n",
    "        \n",
    "        for querie in queries :\n",
    "            tmp = 0\n",
    "            for i, left in enumerate(degree[1:], 1) :\n",
    "                j = bisect.bisect(degree, querie - left, i + 1)\n",
    "                tmp += n - j + 1\n",
    "            for i,cnt in adj.items() :\n",
    "                for j, c in cnt.items() :\n",
    "                    if i < j and Vcnt[i] + Vcnt[j] > querie and Vcnt[i] + Vcnt[j] - c <= querie :\n",
    "                        tmp -= 1\n",
    "            res.append(tmp)\n",
    "        return res   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        nums = [Counter() for _ in range(n)]\n",
    "        size = [0]*n\n",
    "        for i,j in edges:\n",
    "            i -= 1;j -= 1\n",
    "            nums[i][j] += 1;nums[j][i] += 1\n",
    "            size[i] += 1;size[j] += 1\n",
    "        mx = size[:]\n",
    "        size.sort()\n",
    "        ans = [0]*(len(queries))\n",
    "        for i in range(n):\n",
    "            lin = []\n",
    "            for j in nums[i]:\n",
    "                lin.append((mx[j],mx[j]-nums[i][j]))\n",
    "            lin.sort()\n",
    "            m = mx[i]\n",
    "            for j in range(len(queries)):\n",
    "                q = queries[j]\n",
    "                bi = bisect.bisect_right(size,q-m)\n",
    "                ans[j] += n-bi if m <= q-m else n-bi-1\n",
    "                for k in range(len(lin)-1,-1,-1):\n",
    "                    if lin[k][0] <= q-m:break\n",
    "                    if lin[k][1] <= q-m:ans[j] -= 1\n",
    "        return [x//2 for x in ans]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        de = [0] * (n + 1)\n",
    "        s = defaultdict(Counter)\n",
    "        for x, y in edges:\n",
    "            de[x] += 1\n",
    "            de[y] += 1\n",
    "            # s[tuple(sorted(x, y))] += 1\n",
    "            s[x][y] += 1\n",
    "            s[y][x] += 1\n",
    "        arr = []\n",
    "        for i, v in enumerate(de):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            arr.append((v, i))\n",
    "        arr.sort()\n",
    "        # print(arr, s)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            a = 0\n",
    "            for ii, (v, i) in enumerate(arr):\n",
    "                idx = bisect.bisect(arr, (q - v + 1, 0))\n",
    "                a += n - idx\n",
    "                if idx <= ii:\n",
    "                    a -= 1\n",
    "                # print(v, i, idx, n - idx,q, a)\n",
    "                for k in s[i]:\n",
    "                    if de[k] >= q - v + 1:\n",
    "                        if v + de[k] - s[i][k] <= q:\n",
    "                            a -= 1\n",
    "                            # print(i, de[k], s[i][k], k)\n",
    "            ans.append(a // 2)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        \n",
    "        c = collections.Counter()\n",
    "        d = collections.Counter()\n",
    "        for x, y in edges:\n",
    "            c[x - 1] += 1\n",
    "            c[y - 1] += 1\n",
    "            x, y = min(x, y), max(x, y)\n",
    "            d[(x - 1, y - 1)] += 1\n",
    "        a = [c[x] for x in range(n)]\n",
    "        a.sort()\n",
    "        ret = [0] * len(queries)\n",
    "        for i in range(n):\n",
    "            for j in range(len(queries)):\n",
    "                t = queries[j] + 1 - c[i]\n",
    "                p = bisect.bisect_left(a, t)\n",
    "                ret[j] += n - p\n",
    "                if t <= c[i]:\n",
    "                    ret[j] -= 1\n",
    "        for j in range(len(queries)):\n",
    "            ret[j] //= 2\n",
    "        for x, y in d:\n",
    "            for j in range(len(queries)):\n",
    "                if c[x] + c[y] > queries[j] >= c[x] + c[y] - d[(x, y)]:\n",
    "                    ret[j] -= 1\n",
    "        return ret\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        c = collections.Counter()\n",
    "        d = collections.Counter()\n",
    "        for x, y in edges:\n",
    "            c[x - 1] += 1\n",
    "            c[y - 1] += 1\n",
    "            x, y = min(x, y), max(x, y)\n",
    "            d[(x - 1, y - 1)] += 1\n",
    "        a = [c[x] for x in range(n)]\n",
    "        a.sort()\n",
    "        ret = [0] * len(queries)\n",
    "        for i in range(n):\n",
    "            for j in range(len(queries)):\n",
    "                t = queries[j] + 1 - c[i]\n",
    "                p = bisect.bisect_left(a, t)\n",
    "                ret[j] += n - p\n",
    "                if t <= c[i]:\n",
    "                    ret[j] -= 1\n",
    "        for j in range(len(queries)):\n",
    "            ret[j] //= 2\n",
    "        for x, y in d:\n",
    "            for j in range(len(queries)):\n",
    "                if c[x] + c[y] > queries[j] >= c[x] + c[y] - d[(x, y)]:\n",
    "                    ret[j] -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * (n + 1)\n",
    "        \n",
    "        nEdges = len(edges)\n",
    "        overlap = defaultdict(int)\n",
    "        distinctEdges = []\n",
    "        \n",
    "        def encode(a, b, n):\n",
    "            return max(a, b) * (n + 1) + min(a, b)\n",
    "        \n",
    "        for i in range(nEdges):\n",
    "            p, q = edges[i]\n",
    "            deg[p] += 1\n",
    "            deg[q] += 1\n",
    "            idx = encode(p, q, n)\n",
    "            if overlap[idx] == 0:\n",
    "                distinctEdges.append([p, q])\n",
    "            overlap[idx] += 1\n",
    "\n",
    "        sortedDeg = sorted(deg[1:])\n",
    "        \n",
    "        nQueries = len(queries)\n",
    "        ret = [0] * nQueries\n",
    "        for i in range(nQueries):\n",
    "            l, r = 0, n - 1\n",
    "            cnt = 0\n",
    "            while l < n:\n",
    "                while r > l and sortedDeg[l] + sortedDeg[r] > queries[i]:\n",
    "                    r -= 1\n",
    "                cnt += (n - max(l, r) - 1)\n",
    "                l += 1\n",
    "\n",
    "            for j in range(len(distinctEdges)):\n",
    "                p, q = distinctEdges[j]\n",
    "                idx = encode(p, q, n)\n",
    "                if deg[p] + deg[q] > queries[i] and deg[p] + deg[q] - overlap[idx] <= queries[i]:\n",
    "                    cnt -= 1\n",
    "            ret[i] = cnt\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * (n + 1)\n",
    "        nEdges = len(edges)\n",
    "        overlap = defaultdict(int)\n",
    "        distinctEdges = []\n",
    "        def encode(a, b, n):\n",
    "            return max(a, b) * (n + 1) + min(a, b)\n",
    "\n",
    "        for i in range(nEdges):\n",
    "            p, q = edges[i]\n",
    "            deg[p] += 1\n",
    "            deg[q] += 1\n",
    "            idx = encode(p, q, n)\n",
    "            if overlap[idx] == 0:\n",
    "                distinctEdges.append([p, q])\n",
    "            overlap[idx] += 1\n",
    "\n",
    "        sortedDeg = sorted(deg[1:])\n",
    "        nQueries = len(queries)\n",
    "        ret = [0] * nQueries\n",
    "        for i in range(nQueries):\n",
    "            l, r = 0, n - 1\n",
    "            cnt = 0\n",
    "            while l < n:\n",
    "                while r > l and sortedDeg[l] + sortedDeg[r] > queries[i]:\n",
    "                    r -= 1\n",
    "                cnt += (n - max(l, r) - 1)\n",
    "                l += 1\n",
    "\n",
    "            for j in range(len(distinctEdges)):\n",
    "                p, q = distinctEdges[j]\n",
    "                idx = encode(p, q, n)\n",
    "                if deg[p] + deg[q] > queries[i] and deg[p] + deg[q] - overlap[idx] <= queries[i]:\n",
    "                    cnt -= 1\n",
    "            ret[i] = cnt\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        def f(x,y):return x*n+y if x < y else y*n+x\n",
    "        has = Counter()\n",
    "        nums = [[] for _ in range(n)]\n",
    "        size = [0]*n\n",
    "        for i,j in edges:\n",
    "            i -= 1;j -= 1\n",
    "            has[f(i,j)] += 1\n",
    "            if has[f(i,j)] == 1:\n",
    "                nums[i].append(j);nums[j].append(i)\n",
    "            size[i] += 1;size[j] += 1\n",
    "        mx = size[:]\n",
    "        size.sort()\n",
    "        ans = [0]*(len(edges))\n",
    "        qq = list(set(queries))\n",
    "        for i in range(n):\n",
    "            lin = []\n",
    "            for j in nums[i]:\n",
    "                lin.append((mx[j],mx[j]-has[f(i,j)]))\n",
    "            lin.sort()\n",
    "            m = mx[i]\n",
    "            for q in qq:\n",
    "                bi = bisect.bisect_right(size,q-m)\n",
    "                ans[q] += n-bi if m <= q-m else n-bi-1\n",
    "                for k in range(len(lin)-1,-1,-1):\n",
    "                    if lin[k][0] <= q-m:break\n",
    "                    if lin[k][1] <= q-m:ans[q] -= 1\n",
    "        return [ans[x]//2 for x in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        ad = [0] * n\n",
    "        neibors = [defaultdict(int) for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            ad[x] += 1\n",
    "            ad[y] += 1\n",
    "            neibors[y][x] += 1\n",
    "            neibors[x][y] += 1\n",
    "\n",
    "        s = sorted(range(n), key = lambda x: ad[x])\n",
    "        vs = [0] * n\n",
    "        for i, k in enumerate(s):\n",
    "            vs[k] = i\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            l, r = 0, n - 1\n",
    "            while l < r:\n",
    "                while l < r and ad[s[l]] + ad[s[r]] <= queries[i]:\n",
    "                    l += 1\n",
    "                ans[i] += r - l \n",
    "                nei = neibors[s[r]]\n",
    "                for x in nei:\n",
    "                    if vs[x] > r:\n",
    "                        continue\n",
    "                    if vs[x] >= l:\n",
    "                        ans[i] -= 1\n",
    "                    if ad[s[r]] + ad[x] - nei[x] > queries[i]:\n",
    "                        ans[i] += 1\n",
    "                r -= 1\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n",
    "                \n",
    "                 \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        def f(x,y):return x*n+y if x < y else y*n+x\n",
    "        has = Counter()\n",
    "        nums = [[] for _ in range(n)]\n",
    "        size = [0]*n\n",
    "        for i,j in edges:\n",
    "            i -= 1;j -= 1\n",
    "            size[i] += 1;size[j] += 1\n",
    "            has[f(i,j)] += 1\n",
    "            if has[f(i,j)] == 1:\n",
    "                nums[i].append(j)\n",
    "                nums[j].append(i)\n",
    "        mx = size[:]\n",
    "        size.sort()\n",
    "        ans = [0]*(len(queries))\n",
    "        for m in mx:\n",
    "            for idx in range(len(queries)):\n",
    "                q = queries[idx]\n",
    "                bi = bisect.bisect_right(size,q-m)\n",
    "                ans[idx] += n-bi if m <= q-m else n-bi-1\n",
    "        for i,x in has.items():\n",
    "            i,j = i//n,i%n\n",
    "            for idx in range(len(queries)):\n",
    "                q = queries[idx]\n",
    "                if mx[i]+mx[j] > q and mx[i]+mx[j]-x <= q:\n",
    "                    ans[idx] -= 2\n",
    "        return [x//2 for x in ans]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        #count = du[a]+du[b]-count[a,b]>q\n",
    "        #if count = 0, du[b]>q-du[a]\n",
    "        du = [0]*(n+1)\n",
    "        count = [{} for i in range(n+1)]\n",
    "        for a, b in edges:\n",
    "            du[a] += 1\n",
    "            du[b] += 1\n",
    "            if b in count[a]:\n",
    "                count[a][b] += 1\n",
    "            else:\n",
    "                count[a][b] = 1\n",
    "            if a in count[b]:\n",
    "                count[b][a] += 1\n",
    "            else:\n",
    "                count[b][a] = 1\n",
    "        sdu = sorted(du[1:])\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            cur = 0\n",
    "            for a in range(1, n+1):\n",
    "                cur += n-bisect_right(sdu, q - du[a])\n",
    "                if du[a] > q-du[a]:\n",
    "                    cur -= 1\n",
    "                for b, v in count[a].items():\n",
    "                    if du[b] > q-du[a]:\n",
    "                        cur -= 1\n",
    "                    if du[a]+du[b]-v > q:\n",
    "                        cur += 1\n",
    "            res.append(cur//2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        has = Counter()\n",
    "        nums = [Counter() for _ in range(n)]\n",
    "        size = [0]*n\n",
    "        for i,j in edges:\n",
    "            i -= 1;j -= 1\n",
    "            nums[i][j] += 1\n",
    "            nums[j][i] += 1\n",
    "            size[i] += 1;size[j] += 1\n",
    "        mx = size[:]\n",
    "        size.sort()\n",
    "        ans = [0]*(len(edges))\n",
    "        qq = list(set(queries))\n",
    "        for i in range(n):\n",
    "            lin = []\n",
    "            for j in nums[i]:\n",
    "                lin.append((mx[j],mx[j]-nums[i][j]))\n",
    "            lin.sort()\n",
    "            m = mx[i]\n",
    "            for q in qq:\n",
    "                bi = bisect.bisect_right(size,q-m)\n",
    "                ans[q] += n-bi if m <= q-m else n-bi-1\n",
    "                for k in range(len(lin)-1,-1,-1):\n",
    "                    if lin[k][0] <= q-m:break\n",
    "                    if lin[k][1] <= q-m:ans[q] -= 1\n",
    "        return [ans[x]//2 for x in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef countPairs(self, n, edges, queries):\n",
    "\t\tg = [defaultdict(int) for _ in range(n)]\n",
    "\t\td = [0] * n\n",
    "\t\tfor u, v in edges:\n",
    "\t\t\tg[u - 1][v - 1] += 1; g[v - 1][u - 1] += 1\n",
    "\t\t\td[u - 1] += 1; d[v - 1] += 1\n",
    "\t\to = sorted(d)\n",
    "\t\tans = [0] * len(queries)\n",
    "\t\tfor i, q in enumerate(queries):\n",
    "\t\t\tr = 0\n",
    "\t\t\tfor u in range(n):\n",
    "\t\t\t\tans[i] += n - bisect_left(o, q + 1 - d[u])\n",
    "\t\t\t\tif d[u] + d[u] >= q + 1: ans[i] -= 1\n",
    "\t\t\t\tfor v, c in g[u].items():\n",
    "\t\t\t\t\tif d[u] + d[v] > q and d[u] + d[v] - c <= q: ans[i] -= 1\n",
    "\t\t\tans[i] //= 2\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        num = [0] * n\n",
    "        d = [{} for i in range(n)]\n",
    "        idx = [i for i in range(n)]\n",
    "        for edge in edges:\n",
    "            a = edge[0] - 1\n",
    "            b = edge[1] - 1\n",
    "            num[a] += 1\n",
    "            num[b] += 1\n",
    "            if d[a].get(b) == None:\n",
    "                d[a][b] = 0\n",
    "            d[a][b] += 1\n",
    "            if d[b].get(a) == None:\n",
    "                d[b][a] = 0\n",
    "            d[b][a] += 1\n",
    "        idx.sort(key = lambda i : num[i])\n",
    "        ridx = [0] * n\n",
    "        for i in range(n):\n",
    "            ridx[idx[i]] = i\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            l = 0\n",
    "            nowAns = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                if l >= i:\n",
    "                    break\n",
    "                while l < i and num[idx[l]] + num[idx[i]] <= query:\n",
    "                    l += 1\n",
    "                nowAns += i - l\n",
    "                for k, v in d[idx[i]].items():\n",
    "                    if ridx[k] >= l and ridx[k] < i and num[k] + num[idx[i]] - v <= query:\n",
    "                        nowAns -= 1\n",
    "            ans.append(nowAns)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        num = [0] * n\n",
    "        d = [{} for i in range(n)]\n",
    "        idx = [i for i in range(n)]\n",
    "        for edge in edges:\n",
    "            a = edge[0] - 1\n",
    "            b = edge[1] - 1\n",
    "            num[a] += 1\n",
    "            num[b] += 1\n",
    "            if d[a].get(b) == None:\n",
    "                d[a][b] = 0\n",
    "            d[a][b] += 1\n",
    "            if d[b].get(a) == None:\n",
    "                d[b][a] = 0\n",
    "            d[b][a] += 1\n",
    "        idx.sort(key = lambda i : num[i])\n",
    "        ridx = [0] * n\n",
    "        for i in range(n):\n",
    "            ridx[idx[i]] = i\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            l = 0\n",
    "            nowAns = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                if l >= i:\n",
    "                    break\n",
    "                while l < i and num[idx[l]] + num[idx[i]] <= query:\n",
    "                    l += 1\n",
    "                nowAns += i - l\n",
    "                for k, v in d[idx[i]].items():\n",
    "                    if ridx[k] >= l and ridx[k] < i and num[k] + num[idx[i]] - v <= query:\n",
    "                        nowAns -= 1\n",
    "            ans.append(nowAns)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPairs(self, n, edges, queries):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type edges: List[List[int]]\n",
    "        :type queries: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dicsort=list()\n",
    "        dic=dict()\n",
    "        for edge in edges:\n",
    "            if dic.get(edge[0],None)==None:\n",
    "                dic[edge[0]]={edge[1]:1,'len':1}\n",
    "            else:\n",
    "                dic[edge[0]][edge[1]]=dic[edge[0]].get(edge[1],0)+1\n",
    "                dic[edge[0]]['len']+=1\n",
    "            if dic.get(edge[1],None)==None:\n",
    "                dic[edge[1]]={edge[0]:1,'len':1}\n",
    "            else:\n",
    "                dic[edge[1]][edge[0]]=dic[edge[1]].get(edge[0],0)+1\n",
    "                dic[edge[1]]['len']+=1\n",
    "        for i in range(1,n+1):\n",
    "            if i in dic:\n",
    "                dicsort.append([i,dic[i]['len']])\n",
    "            else:\n",
    "                dicsort.append([i,0])\n",
    "        dicsort.sort(key=lambda x:x[1])\n",
    "        print(dicsort)\n",
    "        for k,target in enumerate(queries):\n",
    "            count=0\n",
    "            for i in dicsort:\n",
    "                derta=target-i[1]\n",
    "                left,right=0,len(dicsort)-1\n",
    "                if dicsort[right][1]<=derta:\n",
    "                    continue\n",
    "                elif dicsort[left][1]>derta:\n",
    "                    count+=n\n",
    "                else:\n",
    "                    while right-left>1:\n",
    "                        mid=(left+right)//2\n",
    "                        if dicsort[mid][1]<=derta:\n",
    "                            left=mid\n",
    "                        elif dicsort[mid][1]>derta:\n",
    "                            right=mid\n",
    "                        else:\n",
    "                            while dicsort[mid][1]==derta:\n",
    "                                mid+=1\n",
    "                            right=mid\n",
    "                            break\n",
    "                    count+=n-right\n",
    "                for edge in dic.get(i[0],[]):\n",
    "                    if edge!='len' and i[1]-dic[i[0]][edge]+dic[edge]['len']<=target and i[1]+dic[edge]['len']>target:\n",
    "                        count-=1\n",
    "                if i[1]+i[1]>target:\n",
    "                    count-=1\n",
    "            queries[k]=count//2 \n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPairs(self, n, edges, queries):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type edges: List[List[int]]\n",
    "        :type queries: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dicsort=list()\n",
    "        dic=dict()\n",
    "        for edge in edges:\n",
    "            if dic.get(edge[0],None)==None:\n",
    "                dic[edge[0]]={edge[1]:1,'len':1}\n",
    "            else:\n",
    "                dic[edge[0]][edge[1]]=dic[edge[0]].get(edge[1],0)+1\n",
    "                dic[edge[0]]['len']+=1\n",
    "            if dic.get(edge[1],None)==None:\n",
    "                dic[edge[1]]={edge[0]:1,'len':1}\n",
    "            else:\n",
    "                dic[edge[1]][edge[0]]=dic[edge[1]].get(edge[0],0)+1\n",
    "                dic[edge[1]]['len']+=1\n",
    "        for i in range(1,n+1):\n",
    "            if i in dic:\n",
    "                dicsort.append([i,dic[i]['len']])\n",
    "            else:\n",
    "                dicsort.append([i,0])\n",
    "        dicsort.sort(key=lambda x:x[1])\n",
    "        print(dicsort)\n",
    "        for k,target in enumerate(queries):\n",
    "            count=0\n",
    "            for i in dicsort:\n",
    "                derta=target-i[1]\n",
    "                left,right=0,len(dicsort)-1\n",
    "                if dicsort[right][1]<=derta:\n",
    "                    continue\n",
    "                elif dicsort[left][1]>derta:\n",
    "                    count+=n\n",
    "                else:\n",
    "                    while right-left>1:\n",
    "                        mid=(left+right)//2\n",
    "                        if dicsort[mid][1]<=derta:\n",
    "                            left=mid\n",
    "                        elif dicsort[mid][1]>derta:\n",
    "                            right=mid\n",
    "                        else:\n",
    "                            while dicsort[mid][1]==derta:\n",
    "                                mid+=1\n",
    "                            right=mid\n",
    "                            break\n",
    "                    count+=n-right\n",
    "                for edge in dic.get(i[0],[]):\n",
    "                    if edge!='len' and i[1]-dic[i[0]][edge]+dic[edge]['len']<=target and i[1]+dic[edge]['len']>target:\n",
    "                        count-=1\n",
    "                if i[1]+i[1]>target:\n",
    "                    count-=1\n",
    "            queries[k]=count//2 \n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        cnt=defaultdict(int)\n",
    "        node_sum=[0]*n\n",
    "        for a,b in edges:\n",
    "            a-=1\n",
    "            b-=1\n",
    "            node_sum[a]+=1\n",
    "            node_sum[b]+=1\n",
    "            cnt[(min(a,b),max(a,b))]+=1\n",
    "        node_sum_nums=sorted(node_sum)\n",
    "        res=[]\n",
    "        for quer in queries:\n",
    "            L,R=0,len(node_sum)-1\n",
    "            total=0\n",
    "            while L<R:\n",
    "                tmp_value=node_sum_nums[L]+node_sum_nums[R]\n",
    "                if tmp_value>quer:\n",
    "                    total+=R-L\n",
    "                    R-=1\n",
    "                else:\n",
    "                    L+=1\n",
    "            # 去掉不满足条件的\n",
    "            for (a,b),v in cnt.items():\n",
    "                if node_sum[a]+node_sum[b]>quer and  node_sum[a]+node_sum[b]-v<=quer:\n",
    "                    total-=1\n",
    "            res.append(total)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        def bisearch(val,a,l,r):\n",
    "            mid = r+1\n",
    "            if l>r:\n",
    "                return mid\n",
    "            while l<=r:\n",
    "                mid = (l + r)//2\n",
    "                if a[mid]<=val:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            return mid+1 if a[mid]<=val else mid\n",
    "        ans = [0]*len(queries)\n",
    "        nodes = [0] * n \n",
    "        graph = defaultdict(int)\n",
    "        for a,b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if a>b:\n",
    "                a,b = b,a\n",
    "            nodes[a]+=1\n",
    "            nodes[b]+=1\n",
    "            graph[(a,b)] +=1\n",
    "        lst = sorted(nodes)\n",
    "        for i in range(len(queries)):\n",
    "            for j in range(len(lst)):\n",
    "                r = queries[i]-lst[j]\n",
    "                index = bisearch(r,lst,j+1,len(lst)-1)\n",
    "                print(index)\n",
    "                ans[i]+=n-index\n",
    "            for key in graph:\n",
    "                a,b = key\n",
    "                if nodes[a]+nodes[b]>queries[i] and nodes[a]+nodes[b]-graph[key]<=queries[i]:\n",
    "                    ans[i]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        overlap = dict()\n",
    "        connectedEdges = collections.defaultdict(int)\n",
    "\n",
    "        def getId(edge):\n",
    "            return min(edge) * (2* 10**5+1) + max(edge)\n",
    "        \n",
    "        for i, e in enumerate(edges):\n",
    "            u, v = e[0], e[1]\n",
    "            deg[u-1] += 1\n",
    "            deg[v-1] += 1\n",
    "\n",
    "            if getId(e) not in overlap:\n",
    "                overlap[getId(e)] = i\n",
    "            \n",
    "            connectedEdges[getId(e)] += 1\n",
    "        \n",
    "        ndeg = sorted(deg)\n",
    "        ret = []\n",
    "        for q in queries:\n",
    "            l, r = 0, n-1\n",
    "            cnt = 0\n",
    "            while l < n:\n",
    "                while r > l and ndeg[l] + ndeg[r] > q:\n",
    "                    r -= 1\n",
    "                cnt += n - max(l, r) - 1\n",
    "                l += 1\n",
    "            for i in overlap.values():\n",
    "                u, v = edges[i][0], edges[i][1]\n",
    "                if deg[u-1] + deg[v-1] > q and deg[u-1] + deg[v-1] - connectedEdges[getId(edges[i])] <= q:\n",
    "\n",
    "                    cnt -= 1\n",
    "            ret.append(cnt)\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        graph = collections.Counter()\n",
    "        ind = [0] * n \n",
    "        for a, b in edges:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            graph[(a - 1, b - 1)] += 1\n",
    "            ind[a - 1] += 1 \n",
    "            ind[b - 1] += 1 \n",
    "        sorted_ind = sorted(ind)\n",
    "        def binary_search(start, target):\n",
    "            if sorted_ind[-1] <= target:\n",
    "                return n\n",
    "            l = start\n",
    "            r = n - 1 \n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 \n",
    "                if sorted_ind[mid] <= target:\n",
    "                    l = mid + 1 \n",
    "                else:\n",
    "                    r = mid \n",
    "            return l \n",
    "        res = []\n",
    "        for q in queries:\n",
    "            ans = 0\n",
    "            for i in range(n - 1):\n",
    "                idx = binary_search(i + 1, q - sorted_ind[i])\n",
    "                ans += n - idx \n",
    "            for a, b in graph:\n",
    "                if ind[a] + ind[b] > q and ind[a] + ind[b] - graph[(a, b)] <= q:\n",
    "                    ans -= 1 \n",
    "            res.append(ans)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        graph = collections.Counter()\n",
    "        ind = [0] * n \n",
    "        for a, b in edges:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            graph[(a - 1, b - 1)] += 1\n",
    "            ind[a - 1] += 1 \n",
    "            ind[b - 1] += 1 \n",
    "        sorted_ind = sorted(ind)\n",
    "        def binary_search(start, target):\n",
    "            if sorted_ind[-1] <= target:\n",
    "                return n\n",
    "            l = start\n",
    "            r = n - 1 \n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 \n",
    "                if sorted_ind[mid] <= target:\n",
    "                    l = mid + 1 \n",
    "                else:\n",
    "                    r = mid \n",
    "            return l \n",
    "        res = []\n",
    "        for q in queries:\n",
    "            ans = 0\n",
    "            for i in range(n - 1):\n",
    "                idx = binary_search(i + 1, q - sorted_ind[i])\n",
    "                ans += n - idx \n",
    "            for a, b in graph:\n",
    "                if ind[a] + ind[b] > q and ind[a] + ind[b] - graph[(a, b)] <= q:\n",
    "                    ans -= 1 \n",
    "            res.append(ans)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            mi, ma = min(y[0], y[1]) - 1, max(y[0], y[1]) - 1\n",
    "            e.setdefault((mi, ma), 0)\n",
    "            e[(mi, ma)] += 1\n",
    "        z = sorted(cnt)\n",
    "        nn = len(z)\n",
    "        dd = dict()\n",
    "        cc = Counter(cnt)\n",
    "        @lru_cache(n)\n",
    "        def findy(jj, i):\n",
    "            if jj > queries[i]:\n",
    "                return n - 1\n",
    "            yy = bisect_right(z, queries[i] - jj)\n",
    "            return nn - yy - (2 * jj > queries[i])\n",
    "        for i in range(len(queries)):\n",
    "            if i in dd:\n",
    "                res[i] = dd[i]\n",
    "                continue\n",
    "            for j, ccc in cc.items():\n",
    "                res[i] += findy(j, i) * ccc\n",
    "            for edg, v in e.items():\n",
    "                if queries[i] < cnt[edg[0]] + cnt[edg[1]] <= v + queries[i]:\n",
    "                    res[i] -= 2\n",
    "            res[i] = res[i]// 2\n",
    "            dd[i] = res[i]\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degree = [0 for i in range(n)]\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for edge in edges:\n",
    "            if edge[0] > edge[1]:\n",
    "                edge[1], edge[0] = edge[0], edge[1]\n",
    "            degree[edge[0] - 1] += 1\n",
    "            degree[edge[1] - 1] += 1\n",
    "            cnt[(edge[0] - 1, edge[1] - 1)] += 1\n",
    "        \n",
    "        arr = sorted(degree)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            ans = 0\n",
    "            i, j = 0, n - 1\n",
    "            while i < n:\n",
    "                while arr[i] + arr[j] > q and j > i:\n",
    "                    j -= 1\n",
    "                ans += n - 1 - max(i, j)\n",
    "                i += 1\n",
    "            for (x, y), freq in cnt.items():\n",
    "                if degree[x] + degree[y] > q and degree[x] + degree[y] - freq <= q:\n",
    "                    ans -= 1\n",
    "            res.append(ans)\n",
    "\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = defaultdict(set)\n",
    "        res = [0] * len(queries)\n",
    "        cnt = [0] * n\n",
    "        e = dict()\n",
    "        for y in edges:\n",
    "            cnt[y[0]-1] += 1\n",
    "            cnt[y[1]-1] += 1\n",
    "            e.setdefault(y[0]-1, dict())\n",
    "            e.setdefault(y[1]-1, dict())\n",
    "            e[y[0]-1].setdefault(y[1]-1, 0)\n",
    "            e[y[1]-1].setdefault(y[0]-1, 0)\n",
    "            e[y[0]-1][y[1]-1] += 1\n",
    "            e[y[1]-1][y[0]-1] += 1\n",
    "        from sortedcontainers import SortedList\n",
    "        yy = SortedList(cnt)\n",
    "        for i in range(len(queries)):\n",
    "            z = yy.copy()\n",
    "            for x, j in enumerate(cnt):\n",
    "                if j > queries[i]:\n",
    "                    res[i] += n - 1 - x\n",
    "                    z.pop(z.index(j))\n",
    "                    continue\n",
    "                z.pop(z.index(j))\n",
    "                y = z.bisect_right(queries[i] - j)\n",
    "                res[i] += len(z) - y\n",
    "                if x in e:\n",
    "                    for edg in e[x]:\n",
    "                        if edg > x and cnt[edg] + j - e[x][edg] <= queries[i] and cnt[edg] + j > queries[i]:\n",
    "                            res[i] -= 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        g = [Counter() for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            g[a][b] += 1\n",
    "            g[b][a] += 1\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i:deg[i])\n",
    "        pos = [0] * n\n",
    "        for i in range(n):\n",
    "            pos[idx[i]] = i\n",
    "         # print(idx, [deg[i] for i in idx])\n",
    "        ret = [0] * len(queries)\n",
    "        \n",
    "        for k, q in enumerate(queries):\n",
    "            l, r = 0, n - 1\n",
    "            while l < r:\n",
    "                if deg[idx[l]] + deg[idx[r]] > q:\n",
    "                    ret[k] += r - l\n",
    "                    need = q + 1 - deg[idx[r]]\n",
    "                    for son, cnt in g[idx[r]].items():\n",
    "                        if pos[son] < r and deg[son] - cnt < need and deg[son] >= need:\n",
    "                            ret[k] -= 1 \n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1     \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        g = [Counter() for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            g[a][b] += 1\n",
    "            g[b][a] += 1\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i:deg[i])\n",
    "        pos = [0] * n\n",
    "        for i in range(n):\n",
    "            pos[idx[i]] = i\n",
    "         # print(idx, [deg[i] for i in idx])\n",
    "        ret = [0] * len(queries)\n",
    "        for k, q in enumerate(queries):\n",
    "            for i in range(1, n):\n",
    "                need = q + 1 - deg[idx[i]]\n",
    "                need = q - deg[idx[i]] + 1\n",
    "                l, r = 0, i - 1\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if deg[idx[m]] >= need:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                if i == l:\n",
    "                    continue\n",
    "                ret[k] += i - l\n",
    "\n",
    "                for son, cnt in g[idx[i]].items():\n",
    "                    if pos[son] < i and deg[son] - cnt < need and deg[son] >= need:\n",
    "                        ret[k] -= 1              \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * (n)\n",
    "        g = []\n",
    "        for a, b in edges:\n",
    "            a, b = a - 1, b - 1\n",
    "            a, b = min(a, b), max(a, b)\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            g.append((a, b))\n",
    "        sorted_deg = sorted(deg)\n",
    "        cnt = Counter(g)\n",
    "        print(sorted_deg)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            for j, x in enumerate(sorted_deg):\n",
    "                k = bisect_right(sorted_deg, q - x, lo = j + 1)\n",
    "                ans[i] += n - k\n",
    "            for (a, b), t in cnt.items():\n",
    "                if q < deg[a] + deg[b] <= q + t:\n",
    "                    ans[i] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        a = [0] * (n+1)\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        for e in edges:\n",
    "            a[e[0]] += 1\n",
    "            a[e[1]] += 1\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            d[a[i]] += 1\n",
    "        \n",
    "        ans = defaultdict(int)\n",
    "        ds = list(d.keys())\n",
    "        for i in range(len(ds)):\n",
    "            for j in range(i+1):\n",
    "                if i==j:\n",
    "                    ans[ds[i]<<1] += d[ds[i]] * (d[ds[i]]-1) >> 1\n",
    "                else:\n",
    "                    ans[ds[i]+ds[j]] += d[ds[i]] * d[ds[j]]\n",
    "\n",
    "        edges = [tuple(sorted(i)) for i in edges]\n",
    "        cnt = defaultdict(lambda: defaultdict(int))\n",
    "        for e in edges:\n",
    "            cnt[e[0]][e[1]] += 1\n",
    "        \n",
    "        for e in edges:\n",
    "            x, y = e\n",
    "            if cnt[x][y]:\n",
    "                ans[a[x]+a[y]] -= 1\n",
    "                ans[a[x]+a[y]-cnt[x][y]] += 1\n",
    "                cnt[x][y] = 0\n",
    "        \n",
    "        for i in range(max(queries)+2):\n",
    "            ans[i] += ans[i-1]\n",
    "        \n",
    "        al = n * (n-1) >> 1\n",
    "        res = [al - ans[i] for i in queries]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, Counter\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        def count(nums):\n",
    "            sums = 0\n",
    "            for e in nums:\n",
    "                sums += e\n",
    "            return sums\n",
    "\n",
    "        edge = [defaultdict(int) for _ in range(n+1)]\n",
    "        edge_cnt = Counter()\n",
    "        # edges = list(set(edges))\n",
    "        for e in edges:\n",
    "            a, b = e[0], e[1]\n",
    "            if a>b:\n",
    "                a, b = b, a\n",
    "            \n",
    "            edge[a][b] += 1\n",
    "            edge[b][a] += 1\n",
    "            edge_cnt[(a, b)] += 1\n",
    "        # for i in range(n+1):\n",
    "            # v = edges[i].values()\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        ori_n2c = [count(edge[i].values()) for i in range(n+1)]\n",
    "        # print(n2c)\n",
    "        # print(edge_cnt)\n",
    "        n2c = sorted(ori_n2c)\n",
    "        l = len(queries)\n",
    "        ans = [0] * l\n",
    "        # print(n2c)\n",
    "        for k in range(l):\n",
    "            for i in range(1, n+1):\n",
    "                h = i+1\n",
    "                t = n\n",
    "                pos = -1\n",
    "                while t >= h:\n",
    "                    m = (h+t) // 2\n",
    "                    # print(m)\n",
    "                    if n2c[m] > queries[k] - n2c[i]:\n",
    "                        pos = m\n",
    "                        t = m - 1\n",
    "                    else: \n",
    "                        h = m + 1\n",
    "                    # else:\n",
    "                        # t = m\n",
    "                        # break\n",
    "                t += 1\n",
    "                # if n2c[h] == queries[k] - n2c[i]:\n",
    "                if t < n + 1:\n",
    "                # if pos != -1:\n",
    "                    ans[k] += n - t + 1\n",
    "            # print(ans)\n",
    "            for (a,b), cnt in edge_cnt.items():\n",
    "                if ori_n2c[a] + ori_n2c[b] > queries[k] and ori_n2c[a] + ori_n2c[b] - cnt <= queries[k]:\n",
    "                    # print(a,b,cnt)\n",
    "                    ans[k] -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        cnt = {}\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            if x > y: x, y = y, x\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            cnt[x, y] = cnt.get((x, y), 0) + 1\n",
    "        a = sorted(deg[x] + deg[y] for x, y in cnt)\n",
    "        b = sorted(deg[x] + deg[y] - cnt[x, y] for x, y in cnt)\n",
    "        deg.sort()\n",
    "        deg2 = [x + y for x, y in pairwise(deg)]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            if q >= deg2[-1]:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            left = bisect_right(deg, q - deg[-1])\n",
    "            right = bisect_right(deg2, q)\n",
    "            t = comb(n, 2) + comb(right + 1, 2) - n * left\n",
    "            res.append(\n",
    "                t - sum(bisect_right(deg, q - deg[i], i + 1) for i in range(left, right))\n",
    "                + bisect_right(a, q) - bisect_right(b, q)\n",
    "            )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        cnt = Counter()\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            if x > y: x, y = y, x\n",
    "            cnt[x, y] += 1\n",
    "        a, b = [], []\n",
    "        for x, y in cnt:\n",
    "            t = deg[x] + deg[y]\n",
    "            a.append(t)\n",
    "            b.append(t - cnt[x, y])\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        deg.sort()\n",
    "        n2 = comb(n, 2)\n",
    "        q0 = n2 - comb(bisect_right(deg, 0), 2)\n",
    "        deg2 = [x + y for x, y in pairwise(deg)]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            if q >= deg2[-1]:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            if q == 0:\n",
    "                res.append(q0)\n",
    "                continue\n",
    "            left = bisect_right(deg, q - deg[-1])\n",
    "            right = bisect_right(deg2, q)\n",
    "            res.append(\n",
    "                n2 + comb(right + 1, 2) - n * left\n",
    "                - sum(bisect_right(deg, q - deg[i], i + 1) for i in range(left, right))\n",
    "                + bisect_right(a, q) - bisect_right(b, q)\n",
    "            )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        cnt = {}\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            if x > y: x, y = y, x\n",
    "            cnt[x, y] = cnt.get((x, y), 0) + 1\n",
    "        a = sorted(deg[x] + deg[y] for x, y in cnt)\n",
    "        b = sorted(deg[x] + deg[y] - cnt[x, y] for x, y in cnt)\n",
    "        deg.sort()\n",
    "        n2 = comb(n, 2)\n",
    "        q0 = n2 - comb(bisect_right(deg, 0), 2)\n",
    "        deg2 = [x + y for x, y in pairwise(deg)]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            if q >= deg2[-1]:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            if q == 0:\n",
    "                res.append(q0)\n",
    "                continue\n",
    "            left = bisect_right(deg, q - deg[-1])\n",
    "            right = bisect_right(deg2, q)\n",
    "            res.append(\n",
    "                n2 + comb(right + 1, 2) - n * left\n",
    "                - sum(bisect_right(deg, q - deg[i], i + 1) for i in range(left, right))\n",
    "                + bisect_right(a, q) - bisect_right(b, q)\n",
    "            )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        deg = [0] * n\n",
    "        cnt = {}\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            if x > y: x, y = y, x\n",
    "            cnt[x, y] = cnt.get((x, y), 0) + 1\n",
    "        a = sorted(deg[x] + deg[y] for x, y in cnt)\n",
    "        b = sorted(deg[x] + deg[y] - cnt[x, y] for x, y in cnt)\n",
    "        deg.sort()\n",
    "        n2 = comb(n, 2)\n",
    "        q0 = n2 - comb(bisect_right(deg, 0), 2)\n",
    "        deg2 = [x + y for x, y in pairwise(deg)]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            if q >= deg2[-1]:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            if q == 0:\n",
    "                res.append(q0)\n",
    "                continue\n",
    "            left = bisect_right(deg, q - deg[-1])\n",
    "            right = bisect_right(deg2, q)\n",
    "            res.append(\n",
    "                n2 + comb(right + 1, 2) - n * left\n",
    "                - sum(bisect_right(deg, q - deg[i], i + 1) for i in range(left, right))\n",
    "                + bisect_right(a, q) - bisect_right(b, q)\n",
    "            )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "#         degree = [0 for _ in range(n)]\n",
    "#         cnt = collections.defaultdict(int)\n",
    "#         for edge in edges:\n",
    "#             x, y = edge[0] - 1, edge[1] - 1\n",
    "#             if x > y:\n",
    "#                 x, y = y, x\n",
    "#             degree[x] += 1\n",
    "#             degree[y] += 1\n",
    "#             cnt[x * n + y] += 1\n",
    "\n",
    "#         arr = sorted(degree)\n",
    "#         ans = []\n",
    "#         for bound in queries:\n",
    "#             total = 0\n",
    "#             for i in range(n):\n",
    "#                 j = bisect_right(arr, bound - arr[i], i + 1)\n",
    "#                 total += n - j\n",
    "#             for val, freq in cnt.items():\n",
    "#                 x, y = val // n, val % n\n",
    "#                 if degree[x] + degree[y] > bound and degree[x] + degree[y] - freq <= bound:\n",
    "#                     total -= 1\n",
    "#             ans.append(total)\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(\n",
    "        self, n: int, edges: List[List[int]], queries: List[int]\n",
    "    ) -> List[int]:\n",
    "        cnt = [0] * n\n",
    "        g = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            a, b = a - 1, b - 1\n",
    "            a, b = min(a, b), max(a, b)\n",
    "            cnt[a] += 1\n",
    "            cnt[b] += 1\n",
    "            g[(a, b)] += 1\n",
    "\n",
    "        s = sorted(cnt)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, t in enumerate(queries):\n",
    "            for j, x in enumerate(s):\n",
    "                k = bisect_right(s, t - x, lo=j + 1)\n",
    "                ans[i] += n - k\n",
    "            for (a, b), v in g.items():\n",
    "                if cnt[a] + cnt[b] > t and cnt[a] + cnt[b] - v <= t:\n",
    "                    ans[i] -= 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 1. build degree list of undirected graph\n",
    "        edgeCounter = Counter(tuple(sorted([u-1, v-1])) for u, v in edges)\n",
    "        degree = [0] * n \n",
    "        for u, v in edgeCounter:\n",
    "            degree[u] += edgeCounter[(u, v)]\n",
    "            degree[v] += edgeCounter[(u, v)]\n",
    "        \n",
    "        # 2. binary search\n",
    "        sorted_deg = sorted(degree)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            l, r = 0, n-1\n",
    "            while l < r:\n",
    "                if sorted_deg[l] + sorted_deg[r] <= q:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    ans[i] += r-l \n",
    "                    r -= 1 \n",
    "            for (u, v), count in edgeCounter.items():\n",
    "                if q < degree[u] + degree[v] <= q + count:\n",
    "                    ans[i] -= 1\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        degree = [0]*n\n",
    "        freq = defaultdict(int)\n",
    "        for u, v in edges: \n",
    "            degree[u-1] += 1\n",
    "            degree[v-1] += 1\n",
    "            freq[min(u-1, v-1), max(u-1, v-1)] += 1\n",
    "        \n",
    "        vals = sorted(degree)\n",
    "        \n",
    "        ans = []\n",
    "        for query in queries: \n",
    "            cnt = 0 \n",
    "            lo, hi = 0, n-1\n",
    "            while lo < hi: \n",
    "                if query < vals[lo] + vals[hi]: \n",
    "                    cnt += hi - lo # (lo, hi), (lo+1, hi), ..., (hi-1, hi) all valid\n",
    "                    hi -= 1\n",
    "                else: lo += 1\n",
    "            for u, v in freq: \n",
    "                if degree[u] + degree[v] - freq[u, v] <= query < degree[u] + degree[v]: cnt -= 1\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        cnt = [0] * n\n",
    "        g = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            a, b = a - 1, b - 1\n",
    "            a, b = min(a, b), max (a, b)\n",
    "            cnt[a] += 1\n",
    "            cnt[b] += 1\n",
    "            g[(a, b)] += 1\n",
    "        s = sorted(cnt)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, t in enumerate(queries):\n",
    "            for j, x in enumerate(s):\n",
    "                k = bisect_right(s, t - x, lo = j + 1)\n",
    "                ans[i] += n - k\n",
    "            for (a, b), v in g.items():\n",
    "                if cnt[a] + cnt[b] > t and cnt[a] + cnt[b] - v <= t:\n",
    "                    ans[i] -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        # 减值思维\n",
    "        # ans, dic = 0, defaultdict(int)\n",
    "        # for x, y in coordinates: dic[(x,y)] += 1\n",
    "        # for x, y in coordinates:\n",
    "        #     dic[(x,y)] -= 1\n",
    "        #     for i in range(k + 1):\n",
    "        #         p = (i ^ x, (k - i) ^ y)\n",
    "        #         if p in dic: ans += dic[p]\n",
    "        # return ans\n",
    "\n",
    "        # 增值思维\n",
    "        ans, dic = 0, defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                p = (i ^ x, (k - i) ^ y)\n",
    "                if p in dic: ans += dic[p]\n",
    "            dic[(x,y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        for v in coordinates:\n",
    "            for i in range(k+1):\n",
    "                x = i^v[0]\n",
    "                y = (k-i)^v[1]\n",
    "                ans += d.get((x,y),0)\n",
    "            if (v[0],v[1]) not in d:\n",
    "                d[(v[0],v[1])] = 0\n",
    "            d[(v[0],v[1])] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        d = Counter()\n",
    "        for v in coordinates:\n",
    "            for i in range(k+1):\n",
    "                ans += d[i^v[0],(k-i)^v[1]]\n",
    "            d[v[0],v[1]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        # (x1 xor x2) + (y1 xor y2) == k\n",
    "        # 0 <= x1 xor x2 <= k  and 0 <= y1 xor y2 <= k\n",
    "        # 如果 x1 xor x2 = i   y1 xor y2 = k - i\n",
    "        # -> x1 = x2 xor i   y1 = y2 xor i\n",
    "        # 枚举 x2 和 y2 以及\n",
    "        # cnt 记录出现过的坐标\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[(x ^ i, y ^(k - i))]\n",
    "            cnt[(x, y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        # 这是一个典型的需要考虑自己学会分析清楚复杂度的题目\n",
    "        # 朴素的思路里，需要两层for两两比对判断才能知道距离是不是k\n",
    "        # 但是这一题里，k的数值范围小\n",
    "        # 所以这里需要变成\n",
    "        # 点对(X,Y);(U,V);  K == K1 + K2\n",
    "        # 且满足 x^u == k1, y^v == k2\n",
    "        # 那么变成了找 u = k1 ^ x; v = k2 ^ y\n",
    "        # 枚举 k1,k2即可\n",
    "        ans = 0\n",
    "        rec = collections.defaultdict(int)\n",
    "        for x,y in coordinates:\n",
    "            rec[(x,y)] += 1\n",
    "\n",
    "        # 注意重复计数策略，当(X,Y) != (U,V)时候，只是val1 * val2 /2\n",
    "        # 当(X,Y) != (U,V)， 是val * (val - 1) / 2\n",
    "        # 对拍的时候的坑， 注意位运算一定要打括号！！！\n",
    "\n",
    "        for k1 in range(0, k+1):\n",
    "            k2 = k - k1 \n",
    "            for x,y in rec.keys():\n",
    "                u, v = (k1 ^ x, k2 ^ y)\n",
    "                val1 = rec.get((x,y), 0)\n",
    "                val2 = rec.get((u,v), 0)\n",
    "                if (x,y) == (u,v):\n",
    "                    ans += val1 * (val1 - 1) / 2\n",
    "                else: \n",
    "                    ans += val1 * val2 / 2\n",
    "        return int(ans) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        dic = {}\n",
    "        \n",
    "        for x,y in coordinates:\n",
    "            if x in dic: dic[x][y] += 1\n",
    "            else: dic[x] = Counter([y])\n",
    "        \n",
    "        ans = 0\n",
    "        for x,y in coordinates:\n",
    "            dic[x][y] -= 1\n",
    "            for i in range(k+1):\n",
    "                m = x ^ i\n",
    "                if m in dic and  k - i >= 0:\n",
    "                    n = (k - i) ^ y\n",
    "                    # print((x,y),\"i\",i,\"m\",m,\"n\",n,\"cnt\",dic[m][n])\n",
    "                    # if m in dic:\n",
    "                    ans += dic[m][n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        cnts = Counter()\n",
    "        ans = 0\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k+1):\n",
    "                x1, y1 = x^i, (k - i) ^ y\n",
    "                ans += cnts[x1, y1]\n",
    "            cnts[x, y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        d = Counter([(x, y) for x, y in coordinates])\n",
    "        print(d)\n",
    "\n",
    "        ret = 0\n",
    "        for (x1, y1), cnt in d.items():\n",
    "            for i in range(k+1):\n",
    "                x2 = i ^ x1\n",
    "                y2 = (k-i) ^ y1\n",
    "                if (x2, y2) in d:\n",
    "                    if (x1, y1) == (x2, y2):\n",
    "                        # ret += int(math.perm(cnt, 2))\n",
    "                        ret += cnt * (cnt - 1)\n",
    "                    else:\n",
    "                        ret += cnt * d[(x2, y2)]\n",
    "\n",
    "        return ret // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, a: List[List[int]], k: int) -> int:\n",
    "        n = len(bin(k)[2:])\n",
    "       \n",
    "        if k==0:\n",
    "            n = 0   \n",
    "        t = (1<<n)\n",
    "        ans = 0\n",
    "        def f(x):\n",
    "            if x>=t:\n",
    "                res = x>>n \n",
    "                res = res<<n\n",
    "                pre = bin(x>>n)[2:]\n",
    "                res = x - res \n",
    "                return [pre, res]\n",
    "                \n",
    "            else:\n",
    "                return ['s', x]\n",
    "            \n",
    "            \n",
    "        def p(x, y)  :\n",
    "            return (x[0]^y[0]) + (x[1]^y[1])\n",
    "        def g(x):\n",
    "            ans = 0\n",
    "            tmp = Counter()\n",
    "            for i, j in x:\n",
    "                tmp[(i, j)] += 1 \n",
    "            l = list(tmp.keys())\n",
    "            for i in range(len(l)):\n",
    "                for j in range(i+1, len(l)):\n",
    "                    if p(l[i], l[j])==k:\n",
    "                        ans += tmp[l[i]]*tmp[l[j]] \n",
    "            for j in tmp:\n",
    "                if p(j, j)==k:\n",
    "                    u = tmp[j]\n",
    "                    u = u*(u-1)//2\n",
    "                    ans += u \n",
    "            return ans \n",
    "            \n",
    "            \n",
    "        b = defaultdict(list)\n",
    "        for x, y in a:\n",
    "            c = f(x)\n",
    "            d = f(y)\n",
    "            b[(c[0], d[0])].append([c[1], d[1]]) \n",
    "        for j in b.values():\n",
    "            ans += g(j)\n",
    "        return ans \n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], _k: int) -> int:\n",
    "        hmap = {}\n",
    "        res = 0\n",
    "        for pair in coordinates:\n",
    "            first = self.first_key(pair)\n",
    "            if first in hmap:\n",
    "                bucket = hmap[first]\n",
    "                for k in bucket:\n",
    "                    if (pair[0] ^ (first[0] + k[0])) + (pair[1] ^ (first[1] + k[1])) == _k:\n",
    "                        res += bucket[k]\n",
    "            self.insert(hmap, pair)\n",
    "        return res\n",
    "\n",
    "    def first_key(self, pair: List[int]):\n",
    "        return (pair[0] & ~127, pair[1] & ~127)\n",
    "    def secord_key(self, pair: List[int]):\n",
    "        return (pair[0] & 127, pair[1] & 127)\n",
    "\n",
    "    def insert(self, hmap, pair: List[int]):\n",
    "        first = self.first_key(pair)\n",
    "        second = self.secord_key(pair)\n",
    "        \n",
    "        if first not in hmap:\n",
    "            hmap[first] = {}\n",
    "        if second not in hmap[first]:\n",
    "            hmap[first][second] = 0\n",
    "        hmap[first][second] += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "#         ans = 0\n",
    "#         n = len(coordinates)\n",
    "#         cnt = Counter()\n",
    "\n",
    "#         for x,y in coordinates:\n",
    "#             for i in range(k+1):\n",
    "#                 ans += cnt[x^i, y^(k-i)]\n",
    "#             cnt[x,y] += 1\n",
    "\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        b7 = 0b11111_11\n",
    "        f13 = 0b11111_11111_11100_00000\n",
    "        di = collections.defaultdict(collections.Counter)        \n",
    "        ans = 0\n",
    "        for i, (x, y) in enumerate(coordinates):\n",
    "            fx, bx = x & f13, x & b7\n",
    "            fy, by = y & f13, y & b7\n",
    "            key, val = (fx, fy), (bx, by)\n",
    "            for (sx, sy), s in di[key].items():\n",
    "                if (bx ^ sx) + (by ^ sy) == k:\n",
    "                    ans += s\n",
    "            di[key][val] += 1\n",
    "        # print(di)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        # 二进制前10位的组合共有1024种\n",
    "        dict_ = defaultdict(list)\n",
    "        for x, y in coordinates:\n",
    "            pair = x >> 10, y >> 10\n",
    "            dict_[pair].append((x & 1023, y & 1023))\n",
    "        ans = 0\n",
    "        for pairs in dict_.values():\n",
    "            if len(pairs) < 2: continue\n",
    "            counter = Counter(pairs)\n",
    "            keys = list(counter.keys())\n",
    "            for i, (x1, y1) in enumerate(keys):\n",
    "                if (x1 ^ x1) + (y1 ^ y1) == k:\n",
    "                    ans += counter[(x1, y1)] * (counter[(x1, y1)] - 1) // 2\n",
    "                for x2, y2 in keys[i + 1:]:\n",
    "                    if (x1 ^ x2) + (y1 ^ y2) == k:\n",
    "                        ans += counter[(x1, y1)] * counter[(x2, y2)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        b7 = 0b11111_11\n",
    "        f13 = 0b11111_11111_11100_00000\n",
    "        di = collections.defaultdict(collections.Counter)        \n",
    "        ans = 0\n",
    "        for i, (x, y) in enumerate(coordinates):\n",
    "            fx, bx = x & f13, x & b7\n",
    "            fy, by = y & f13, y & b7\n",
    "            key, val = (fx, fy), (bx, by)\n",
    "            for (sx, sy), s in di[key].items():\n",
    "                if (bx ^ sx) + (by ^ sy) == k:\n",
    "                    ans += s\n",
    "            di[key][val] += 1\n",
    "        # print(di)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        def check(x, y):\n",
    "            # print(x, y)\n",
    "            return ((x[0]^y[0]) + (x[1]^y[1])) == k\n",
    "        \n",
    "        digit = 0\n",
    "        kk = k\n",
    "        while kk:\n",
    "            kk >>= 1\n",
    "            digit += 1\n",
    "        mk = (1>>digit)-1\n",
    "        # print(\"digit\", digit, mk)\n",
    "        a = defaultdict(Counter)\n",
    "        for i, j in coordinates:\n",
    "            pos = (i>>digit) * 1000000 + (j>>digit)\n",
    "            a[pos][(i&mk, j&mk)] += 1\n",
    "        res = 0\n",
    "        # print(a)\n",
    "        for _, dic in a.items():\n",
    "            # print(dic)\n",
    "            lis = list(dic.keys())\n",
    "            for i in range(len(lis)):\n",
    "                if check(lis[i], lis[i]):\n",
    "                    res += (dic[lis[i]] * (dic[lis[i]]-1))//2\n",
    "                    # print(1, res)\n",
    "                for j in range(i+1, len(lis)):\n",
    "                    if check(lis[i], lis[j]):\n",
    "                        # print(dic, i, j)\n",
    "                        res += dic[lis[i]] * dic[lis[j]]\n",
    "                        # print(2, res)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        res = 0\n",
    "        dct_x = defaultdict(lambda: defaultdict(Counter))\n",
    "        for x,y in coordinates:\n",
    "            for x2,d2 in dct_x[x>>7].items():\n",
    "                if x^x2<=k:\n",
    "                    y2 = (k-(x^x2))^y\n",
    "                    res += d2[y2]\n",
    "            dct_x[x>>7][x][y]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        b10 = 0b11111_11111\n",
    "        f10 = 0b11111_11111_00000_00000\n",
    "        di = defaultdict(Counter)        \n",
    "        ans = 0\n",
    "        for i, (x, y) in enumerate(coordinates):\n",
    "            fx, bx = x & f10, x & b10\n",
    "            fy, by = y & f10, y & b10\n",
    "            key, val = (fx, fy), (bx, by)\n",
    "            for (sx, sy), s in di[key].items():\n",
    "                if (bx ^ sx) + (by ^ sy) == k:\n",
    "                    ans += s\n",
    "            di[key][val] += 1\n",
    "        # print(di)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[((x ^ i) << 20) + (y ^ (k - i))]\n",
    "            cnt[(x << 20) + y] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[((x ^ i) << 20) + (y ^ (k - i))]\n",
    "            cnt[(x << 20) + y] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        def g(x,y):\n",
    "            return x << 20 | y\n",
    "        \n",
    "        st = [g(i,k-i) for i in range(k+1)]\n",
    "        mp = Counter()\n",
    "        ans = 0\n",
    "        for x, y in coordinates:\n",
    "            t = g(x,y)\n",
    "            if t in mp:\n",
    "                ans += mp[t]\n",
    "            for i in st:\n",
    "                mp[i^t] += 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        def g(x,y):\n",
    "            return x << 20 | y\n",
    "        \n",
    "        st = {g(i,k-i) for i in range(k+1)}\n",
    "        mp = Counter()\n",
    "        ans = 0\n",
    "        for x, y in coordinates:\n",
    "            t = g(x,y)\n",
    "            if t in mp:\n",
    "                ans += mp[t]\n",
    "            for i in st:\n",
    "                mp[i^t] += 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k+1):\n",
    "                ans += cnt[(x^i, y^(k-i))]\n",
    "            cnt[(x, y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        num = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for z in range(k+1):\n",
    "                num += cnt[x ^ z, y ^ (k - z)]\n",
    "            cnt[x, y] += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        m = defaultdict(set)\n",
    "        has = set([(a, b) for a, b in coordinates])\n",
    "        for x, y in coordinates:\n",
    "            pass\n",
    "            for a in range(k + 1):\n",
    "                nx = x ^ a\n",
    "                ny = y ^ (k - a)\n",
    "                if (nx, ny) not in has: continue\n",
    "                m[(x, y)].add((nx, ny))\n",
    "\n",
    "        res = 0\n",
    "        count = defaultdict(int)\n",
    "\n",
    "        for info in coordinates:\n",
    "            x1, y1 = info\n",
    "            cur = (x1, y1)\n",
    "\n",
    "            for need in m[cur]:\n",
    "                res += count[need]\n",
    "            count[cur] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        m = defaultdict(set)\n",
    "        has = set([(a, b) for a, b in coordinates])\n",
    "        for x, y in coordinates:\n",
    "            for a in range(k + 1):\n",
    "                nx = x ^ a\n",
    "                ny = y ^ (k - a)\n",
    "                if (nx, ny) not in has: continue\n",
    "                m[(x, y)].add((nx, ny))\n",
    "\n",
    "        res = 0\n",
    "        count = defaultdict(int)\n",
    "\n",
    "        for info in coordinates:\n",
    "            x1, y1 = info\n",
    "            cur = (x1, y1)\n",
    "\n",
    "            for need in m[cur]:\n",
    "                res += count[need]\n",
    "            count[cur] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        if k == 0:\n",
    "            c = collections.Counter()\n",
    "            for x, y in coordinates:\n",
    "                c[(x, y)] += 1\n",
    "            res = 0\n",
    "            for x in c:\n",
    "                res += c[x] * (c[x] - 1) // 2\n",
    "            return res\n",
    "\n",
    "        c = collections.defaultdict(collections.Counter)\n",
    "        for x, y in coordinates:\n",
    "            c[x][y] += 1\n",
    "        res = 0\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(0, x - k), x + k + 1):\n",
    "                v = k - (i ^ x)\n",
    "                if v >= 0:\n",
    "                    w = v ^ y\n",
    "                    res += c[i][w]\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        prev = defaultdict(dict)\n",
    "        n = len(coordinates)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x, y = coordinates[i]\n",
    "            for v in range(k + 1):\n",
    "                t = x ^ v\n",
    "                for (x1, y1), time in prev[t].items():\n",
    "                    if (x1 ^ x) + (y1 ^ y) == k:\n",
    "                        ans += time\n",
    "            if (x, y) not in prev[x]:\n",
    "                prev[x][(x, y)] = 0\n",
    "            prev[x][(x, y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        d = {}\n",
    "        res = 0\n",
    "        for x,y in coordinates:\n",
    "            for i in range(k+1):\n",
    "                x0,y0 = i,k-i\n",
    "                x1,y1 = x^x0,y^y0\n",
    "                if tuple([x1,y1]) in d:\n",
    "                    res += d[tuple([x1,y1])]\n",
    "            if tuple([x,y]) in d:\n",
    "                d[tuple([x,y])] += 1\n",
    "            else:\n",
    "                d[tuple([x,y])] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "    cnt = Counter()\n",
    "    ans = 0\n",
    "    for x, y in coordinates:\n",
    "      for i in range(k + 1):\n",
    "        x1, y1 = x ^ i, y ^ (k - i)\n",
    "        if (x1, y1) in cnt:\n",
    "          ans += cnt[(x1, y1)]\n",
    "      cnt[(x, y)] += 1\n",
    "    return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        d  = defaultdict(int)\n",
    "        for x , y in coordinates:\n",
    "            t = (x, y )\n",
    "            d[t]+=1\n",
    "        ans = 0 \n",
    "        for  v in range(k  +1):\n",
    "            for x, y in d:\n",
    "                nt = ( (x ^ v) , (k - v ) ^ y )\n",
    "                if  nt in d:\n",
    "                    if nt == (x, y ):\n",
    "                        ans+=(d[nt] -  1) *  d[(x,y)]\n",
    "                    else:\n",
    "                        ans +=d[nt] * d[(x,y)]\n",
    "                    \n",
    "        return ans // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, A: List[List[int]], k: int) -> int:\n",
    "        res, mp = 0, Counter()\n",
    "        for x, y in A:\n",
    "            for i in range(k + 1):\n",
    "                res += mp[x ^ i, y ^ (k - i)]\n",
    "            mp[x, y] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        mem=Counter()\n",
    "        ans=0\n",
    "        for x,y in coordinates:\n",
    "            ans+=mem[(x,y)]\n",
    "            for i in range(k+1):\n",
    "                mem[(x^i,y^(k-i))]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        for x,y in coordinates:\n",
    "            for i in range(k+1):\n",
    "                ans+=cnt[x^i, y^(k-i)]\n",
    "            cnt[x,y]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                x1, y1 = x ^ i, y ^ (k - i)\n",
    "                if (x1, y1) in cnt:\n",
    "                    ans += cnt[(x1, y1)]\n",
    "            cnt[(x, y)] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "\n",
    "        n = len(coordinates)\n",
    "        res = 0\n",
    "        mp = Counter()\n",
    "\n",
    "        for i,[x,y] in enumerate(coordinates):\n",
    "            mp[(x,y)]+=1\n",
    "\n",
    "        for i in range(n):\n",
    "            \n",
    "            x,y = coordinates[i][0],coordinates[i][1]\n",
    "            mp[(x,y)]-=1\n",
    "            mp[(x,y)] = max(0,mp[x,y])\n",
    "            for j in range(k+1):\n",
    "                nx = x^j\n",
    "                ny = (k-j)^y\n",
    "                res+=mp[(nx,ny)]\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        for x, y in coordinates:\n",
    "\n",
    "            for i in range(k + 1):\n",
    "\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略\n",
    "\n",
    "            cnt[x, y] += 1  # tuple 的括号可以省略\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        ans=0\n",
    "        for i,j in coordinates:\n",
    "            ans+=d[(i,j)]\n",
    "            for m in range(k+1):\n",
    "                x=m^i\n",
    "                y=(k-m)^j\n",
    "                d[(x,y)]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        cnter = defaultdict(int)\n",
    "        result = 0\n",
    "        for x, y in coordinates:\n",
    "            for j in range(k + 1):\n",
    "                x0, y0 = x ^ j, y ^ (k - j)\n",
    "                result += cnter[x0, y0]\n",
    "                # print(x0, y0)\n",
    "            cnter[x, y] += 1\n",
    "        # print(cnter[1, 3])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        \n",
    "        searchDiff = []\n",
    "        zeros = []\n",
    "        i = 0\n",
    "        while i <= k:\n",
    "            searchDiff.append([i, k-i])\n",
    "            i += 1\n",
    "        print(searchDiff)\n",
    "        for x, y in coordinates:\n",
    "            for dx, dy in searchDiff:\n",
    "                # tup = \n",
    "                ans += cnt[(x ^ dx, y ^ dy)]\n",
    "                # ans += cnt[(x-dx, y+dy)]\n",
    "                # ans += cnt[(x+dx, y-dy)]\n",
    "                # ans += cnt[(x-dx, y-dy)]\n",
    "            print(x,y, ans)\n",
    "            cnt[(x,y)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        res = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k+1):\n",
    "                res += cnt[x^i, y^(k-i)]\n",
    "            cnt[x, y]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for x, y in coordinates:\n",
    "\n",
    "            for i in range(k + 1):\n",
    "\n",
    "                x1, y1 = x ^ i, y ^ (k - i)\n",
    "\n",
    "                if (x1, y1) in cnt:\n",
    "\n",
    "                    ans += cnt[(x1, y1)]\n",
    "\n",
    "            cnt[(x, y)] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, coordinates: List[List[int]], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(k + 1):\n",
    "                ans += cnt[x ^ i, y ^ (k - i)]\n",
    "            cnt[x, y] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
